Maths Olympiad Prep

Library / /28 of 64

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

Compute
log2(a=12015b=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 zn11z^{n_1}-1 are ω,ω2,,ωn1\omega,\omega^2,\ldots,\omega^{n_1}, it follows that
zn11=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
log2(a=12015b=12015(1+e2πiab/2015))=a=12015log2(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)=d2015dϕ(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
dpqrdϕ(pqr/d)=1(p1)(q1)(r1)+p(q1)(r1)+q(p1)(r1)+r(p1)(q1)+pq(r1)+pr(q1)+qr(p1)+pqr1=(2p1)(2q1)(2r1).\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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.