# 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]$

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?

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}}$$