Putnam 2015, Problem A-3

Compute
$$\log_2 \left( \prod_{a=1}^{2015} \prod_{b=1}^{2015} \left(1 + e^{2\pi i ab / 2015}\right) \right)$$
Here $i$ is the imaginary unit (that is, $i^2 = -1$).

Solution:
The answer is 13725. We first claim that if \(n\) is odd, then \(\prod_{b=1}^n (1 + e^{2\pi iab/n}) = 2^{\gcd(a,n)}\). To see this, write \(d = \gcd(a,n)\) and \(a = da_1\), \(n = dn_1\) with \(\gcd(a_1, n_1) = 1\). Then \(a_1, 2a_1, \ldots, n_1a_1\) modulo \(n_1\) is a permutation of \(1, 2, \ldots, n_1\) modulo \(n_1\), and so \(\omega^{a_1}, \omega^{2a_1}, \ldots, \omega^{n_1a_1}\) is a permutation of \(\omega, \omega^2, \ldots, \omega^{n_1}\); it follows that for \(\omega = e^{2\pi i/n_1}\),
\[
\prod_{b=1}^{n_1} (1 + e^{2\pi iab/n}) = \prod_{b=1}^{n_1} (1 + e^{2\pi ia_1b/n_1}) = \prod_{b=1}^{n_1} (1 + \omega^b).
\]
Now since the roots of \(z^{n_1} - 1\) are \(\omega, \omega^2, \ldots, \omega^{n_1}\), it follows that \(z^{n_1} - 1 = \prod_{b=1}^{n_1} (z - \omega^b)\). Setting \(z = -1\) and using the fact that \(n_1\) is odd gives \(\prod_{b=1}^{n_1} (1 + \omega^b) = 2\). Finally, \(\prod_{b=1}^n (1 + e^{2\pi iab/n}) = \left( \prod_{b=1}^{n_1} (1 + e^{2\pi iab/n}) \right)^d = 2^d\), and we have proven the claim.

From the claim, we find that
\[
\log_2 \left( \prod_{a=1}^{2015} \prod_{b=1}^{2015} (1 + e^{2\pi iab/2015}) \right) = \sum_{a=1}^{2015} \log_2 \left( \prod_{b=1}^{2015} (1 + e^{2\pi iab/2015}) \right) = \sum_{a=1}^{2015} \gcd(a, 2015).
\]
Now for each divisor \(d\) of 2015, there are \(\phi(2015/d)\) integers between 1 and 2015 inclusive whose gcd with 2015 is \(d\). Thus
\[
\sum_{a=1}^{2015} \gcd(a, 2015) = \sum_{d|2015} d \cdot \phi(2015/d).
\]
We factor \(2015 = pqr\) with \(p = 5\), \(q = 13\), and \(r = 31\), and calculate
\[
\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 \\
&= (2p-1)(2q-1)(2r-1).
\end{align*}
\]
When \((p, q, r) = (5, 13, 31)\), this is equal to 13725.

Remark: Noam Elkies suggests the following similar but shorter derivation of the equality \(\prod_{b=1}^{n_1} (1 + \omega^b) = 2\): write
\[
\prod_{b=1}^{n_1-1} (1 + \omega^b) = \frac{\prod_{b=1}^{n_1-1} (1 - \omega^{2b})}{\prod_{b=1}^{n_1-1} (1 - \omega^b)}
\]
and note (as above) that \(\omega^2, \omega^4, \ldots, \omega^{2(n_1-1)}\) is a permutation of \(\omega, \ldots, \omega^{n_1-1}\), so the two products in the fraction are equal.