Maths Olympiad Prep

Library / Putnam /27 of 60

Putnam

Number theory Difficulty 7.8 National Olympiad, round 2 Find the answer

Compute
log⁡2(∏a=12015∏b=12015(1+e2πiab/2015)) \log_2 \left( \prod_{a=1}^{2015} \prod_{b=1}^{2015} (1+e^{2\pi i a b/2015}) \right)
Here ii is the imaginary unit (that is, i2=−1i^2=-1).

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

The answer is 1372513725.
We first claim that if nn is odd, then ∏b=1n(1+e2πiab/n)=2gcd⁡(a,n)\prod_{b=1}^{n} (1+e^{2\pi i ab/n}) = 2^{\gcd(a,n)}. To see this, write d=gcd⁡(a,n)d = \gcd(a,n) and a=da1a = da_1, n=dn1n=dn_1 with gcd⁡(a1,n1)=1\gcd(a_1,n_1) = 1. Then
a1,2a1,…,n1a1a_1, 2a_1,\dots,n_1 a_1 modulo n1n_1 is a permutation of 1,2,…,n11,2,\dots,n_1 modulo n1n_1, and so ωa1,ω2a1,…,ωn1a1\omega^{a_1},\omega^{2a_1},\dots,\omega^{n_1 a_1} is a permutation of ω,ω2,…,ωn1\omega,\omega^2,\ldots,\omega^{n_1}; it follows that for ω=e2πi/n1\omega = e^{2\pi i/n_1},
∏b=1n1(1+e2πiab/n)=∏b=1n1(1+e2πia1b/n1)=∏b=1n1(1+ωb). \prod_{b=1}^{n_1} (1+e^{2\pi i a b/n}) = \prod_{b=1}^{n_1} (1+e^{2\pi i a_1 b/n_1}) = \prod_{b=1}^{n_1} (1+\omega^b).
Now since the roots of zn1−1z^{n_1}-1 are ω,ω2,…,ωn1\omega,\omega^2,\ldots,\omega^{n_1}, it follows that
zn1−1=∏b=1n1(z−ωb)z^{n_1}-1 = \prod_{b=1}^{n_1} (z-\omega^b). Setting z=−1z=-1 and using the fact that n1n_1 is odd gives ∏b=1n1(1+ωb)=2\prod_{b=1}^{n_1} (1+\omega^b) = 2.

Finally,
∏b=1n(1+e2πiab/n)=(∏b=1n1(1+e2πiab/n))d=2d\prod_{b=1}^{n} (1+e^{2\pi i ab/n}) = (\prod_{b=1}^{n_1} (1+e^{2\pi i ab/n}))^d = 2^d, and we have proven the claim.

From the claim, we find that
log⁡2(∏a=12015∏b=12015(1+e2πiab/2015))=∑a=12015log⁡2(∏b=12015(1+e2πiab/2015))=∑a=12015gcd⁡(a,2015).\begin{align*} &\log_2 \left( \prod_{a=1}^{2015} \prod_{b=1}^{2015} (1+e^{2\pi i a b/2015}) \right) \\ &= \sum_{a=1}^{2015} \log_2 \left(\prod_{b=1}^{2015} (1+e^{2\pi i a b/2015}) \right) \\ &= \sum_{a=1}^{2015} \gcd(a,2015). \end{align*}
Now for each divisor dd of 20152015, there are ϕ(2015/d)\phi(2015/d) integers between 11 and 20152015 inclusive whose gcd⁡\gcd with 20152015 is dd. Thus
∑a=12015gcd⁡(a,2015)=∑d∣2015d⋅ϕ(2015/d). \sum_{a=1}^{2015} \gcd(a,2015) = \sum_{d|2015} d\cdot \phi(2015/d).
We factor 2015=pqr2015 = pqr with p=5p=5, q=13q=13, and r=31r=31, and calculate
∑d∣pqrd⋅ϕ(pqr/d)=1⋅(p−1)(q−1)(r−1)+p⋅(q−1)(r−1)+q⋅(p−1)(r−1)+r⋅(p−1)(q−1)+pq⋅(r−1)+pr⋅(q−1)+qr⋅(p−1)+pqr⋅1=(2p−1)(2q−1)(2r−1).\begin{align*} &\sum_{d|pqr} d\cdot \phi(pqr/d) \\ &= 1 \cdot (p-1)(q-1)(r-1) + p \cdot (q-1)(r-1) \\ &\quad + q\cdot (p-1)(r-1) + r\cdot (p-1)(q-1) + pq \cdot (r-1) \\ & \quad + pr\cdot (q-1) + qr\cdot (p-1) + pqr \cdot 1 \\ &\quad = (2p-1)(2q-1)(2r-1). \end{align*}
When (p,q,r)=(5,13,31)(p,q,r) = (5,13,31), this is equal to 1372513725.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.