Let the value of $\log_{2} \left[\prod_{a=1}^{2015} \prod_{b=1}^{2015} \left(1+e^{\frac{2 \pi i a b}{2015}}\right)\right]$

Question

Let the value of $$\log_{2} \left[\prod_{a=1}^{2015} \prod_{b=1}^{2015} \left(1+e^{\tfrac{2 \pi i a b}{2015}}\right)\right]$$ is $N$, then which of the following is/are true

(a) $N$ is divisible by $5$

(b) $N$ is divisible by $3$

(c) $N>13000$

(d) $N$ is divisible by $61$

where $i=\sqrt{-1}$

Solution Given: $N=13725$. If $n$ is odd then $\prod_{b=1}^{n}\left(1+e^{\tfrac{2\pi a b i}{n}}\right)=2^{\gcd(a,n)}$

I don't understand how author of this question got the answer.

My Approach: I used $1+e^{i\theta}=2\cos\left(\dfrac{\theta}{2}\right)e^{\tfrac{i\theta}{2}}$

and I got $$\prod_{a=1}^{2015}\left[2\cos\left(\dfrac{\pi a}{2015}\right)\cdot 2\cos\left(\dfrac{2\pi a}{2015}\right)\cdot.....\cdot2\cos\left(\dfrac{2015\pi a}{2015} \right)\cdot e^{i\left(\tfrac{a\pi}{2015}+\tfrac{2a\pi}{2015}+....+\tfrac{2015a\pi}{2015}\right)}\right]$$

But I don't know how to proceed further because of this long product I am stuck.

Also, I thought about $2015$ th root of unity but no help.

Also can anyone explain how did the author got the formula when $n$ is odd?

Answer 1

I shall prove the statement provided by the author. We start with two preliminary claims.

Claim $1$: $\prod_{r=1}^{m} (1+e^{\frac{2i\pi r}{m}}) = 2$ where $m$ is an odd natural integer.

Proof: Consider the $m$-th roots of unity, ie the roots to $x^m-1$. Let $u=e^{\frac{2i\pi}m}$. Then we have $x^m - 1 = \prod_{r=1}^m (x-u^r)$. Setting $x=-1$ gives $2 = \prod_{r=1}^m (1+u^r)$ thereby proving the claim.

Claim $2$: The sequence $\{s_n\}_{n\in \mathbb N}$ where $s_n = an \bmod b$ where $s_n \in \{1,\dots, b\}$ is periodic with period $\frac{b}{\gcd(a,b)}$ where $a$ and $b$ are nautral integers.

Proof: Let $\gcd(a,b) = g$ and $a=ga'$; $b=gb'$. We note that $g | s_n$ so that $s_n = gs_n'$ and hence $s_n' \equiv a'n \pmod {b'}$. Define $S:= \{1,2,\dots, b'\}$. We can take $n\in S$. Now since $\gcd(a',b')=1$, it can be observed that the set of possible values of $s_n'$ over the permissible values of $n$ is the same as $S$ except for the ordering of the elements. So it follows that the period is $b'$ and each period contains exactly the elements $\{g, 2g, 3g, \dots, gb'\}$ in some order.

---

Let $a$ and $b$ be natural integers where $b$ is odd. Define $g=\gcd(a,b)$. Take $a=ga'$ and $b=gb'$. Write $u=e^{2i\pi}$. Note that since $u = 1$, we have $u^{\frac{a}b} = u^{\frac{a\bmod b}b}$. Now

$$\prod_{r=1}^{b} \left(1+u^{\frac{r a}{b}}\right) = \prod_{r=1}^{b} \left(1+u^{\frac{(a'r \bmod b')}{b'}}\right)$$

By claim $2$, it follows that the sequence $\{s_r\}_{r\in[1,b]\cap \mathbb Z}$ with $s_r = a'r \bmod b'$ is periodic with period $b'$. But since $s_r$ contains exactly $b$ elements, $s_r$ contains exactly $\frac{b}{b'} = g$ periods. So the product contains exactly $g$ multiplicands of the same value, ie

$$\left(\prod_{r=1}^{b'} \left(1+u^{\frac{(a'r \bmod b')}{b'}}\right)\right)^g$$

By claim $2$ again, the product $\prod_{r=1}^{b'} \left(1+u^{\frac{a’r \bmod b’}{b'}}\right)$ resolves into $\prod_{r=1}^{b'} \left(1+u^{\frac{r}{b'}}\right)$ since here $\gcd(a',b') = 1$ (read the last line of the claim). By claim $1$, we have $\prod_{r=1}^{b'} \left(1+u^{\frac{r}{b'}}\right) = 2$.

So, the product $$\prod_{r=1}^{b} \left(1+u^{\frac{r a}{b}}\right) = \left(\prod_{r=1}^{b'} \left(1+u^{\frac{a'r}{b'}}\right)\right)^g = 2^g = 2^{\gcd(a,b)}$$

Now we use this to evaluate the product in the question:

$$\prod_{a=1}^{2015} \prod_{b=1}^{2015} \left(1+e^{\tfrac{2 \pi i a b}{2015}}\right) = \prod_{a=1}^{2015} 2^{\gcd(a,2015)}$$ So $\log_2 \prod_{a=1}^{2015} 2^{\gcd(a,2015)} = \sum_{a=1}^{2015} \gcd(a, 2015)$. But notice that the function $f(n) = \sum_{a=1}^n \gcd(a,n)$ is multiplicative, so $f(2015)=f(5)f(13)f(31) = 9\cdot 25\cdot 61 = 13725$.

We conclude $$\boxed{\prod_{a=1}^{2015} \prod_{b=1}^{2015} \left(1+e^{\tfrac{2 \pi i a b}{2015}}\right) = 2^{13725}}$$