Putnam 2015 A3

Problem:

Compute $${\log }_2\left(\prod _{a=1}^{2015}\prod _{b=1}^{2015}(1+e^{2\pi iab/2015})\right)$$

Solution:

We claim that the answer is $\boxed{{\displaystyle 13725}}$.

For a fixed value of $a$, let $w=e^{2\pi iab/2015}$ be a primitive $m^{\text{th}}$ root of unity. Since $\frac{2\pi iab}{2015}=\frac{2\pi i\frac{a}{gcd(a,2015)}b}{\frac{2015}{gcd(a,2015)}}$ in its lowest form, we know that $m=\frac{2015}{gcd(a,2015)}$.

Then, we have

$$\prod _{b=1}^{2015}(1+e^{2\pi iab/2015})=[(1+w)(1+w^2)(1+w^3)\dots (1+w^m){]}^{gcd(a,2015)}(\star ),$$ where the power of $gcd(a,2015)$ is beacuse the cycle $1+w,1+w^2,1+w^3,\dots ,1+w^m$, from $b=1$ to $b=2015$, repeats $\frac{2015}{m}=gcd(a,2015)$ times.

It is well-known that $(x-w)(x-w^2)(x-w^3)\dots (x-w^m)=x^m-1$ for a primitive $m^{\text{th}}$ root of unity, so plugging in $x=-1$, it becomes clear that $$(1+w)(1+w^2)(1+w^3)\dots (1+w^m)=2$$ for odd $m$. 

Using this fact along with $(\star )$, we see that the problem statement is equivalent to $${\log }_2\left(\prod _{a=1}^{2015}{2}^{gcd(a,2015)}\right)=\sum _{a=1}^{2015}gcd(a,2015)$$.

Notice that computing this sum of GCDs is equivalent to computing $$(5+\underset{4\text{ ones}}{\underbrace{1+\cdots +1}})(13+\underset{12\text{ ones}}{\underbrace{1+\cdots +1}})(31+\underset{30\text{ ones}}{\underbrace{1+\cdots +1}})$$

$$=9\cdot 25\cdot 61=13725$$ as desired. $◻$