Putnam 2015/A3

Compute:

\[\log_2\left(\prod_{a=1}^{2015}\prod_{b=1}^{2015}\left(1+e^{2\pi iab/2015}\right)\right)\]

Solution

 First, we use the fact that for any odd integer $m$, we have
\[ \prod_{n=1}^{m} (1 + \omega^n) = 2 \]
where $\omega$ is an $n$th root of unity. Thus
\begin{align*}
    \log_2 \prod_{a=1}^{2015} \prod_{b=1}^{2015}
    \left( 1 + e^{\frac{2\pi i a b}{2015}} \right)
    &= \log_2 \prod_{a=1}^{2015} 2^{\gcd(a,2015)} \\
    &= \sum_{a=1}^{2015} \gcd(a,2015) \\
    &= \sum_{d \mid 2015} \frac{2015}{d} \phi(d) \\
    &= (5+\phi(5))(13+\phi(13))(31+\phi(31)) \\
    &= 9 \cdot 25 \cdot 61 \\
    &= 13725
\end{align*}

The solution can also be found in aops.com