Doubt :$\prod_{b=1}^n(1+\zeta^{ab})=2^k$, where $\zeta = e^{2\pi i/n}$ , $n$ is an odd integer, gcd$(a,n)=k$.

Question

$\prod_{b=1}^n(1+\zeta^{ab})=2^k$, where $\zeta = e^{2\pi i/n}$ , $n$ is an odd integer, gcd$(a,n)=k$.

Can someone explain me why this is true, I got that $\prod_{b=1}^n(1+\zeta^{b})=2$ where $\zeta = e^{2\pi i/n}$

It's from https://artofproblemsolving.com/community/c7h1171025p5624333 post 3.

Thanks in advance!

Answer 1

First we deal with the case with gcd(a,n) = 1. In this case, we know that after multiplying by a, the set of numbers ab still forms a complete residue system, so it is merely a rearrangement of the product $\prod \limits_{b=1}^n(1+\zeta^b)$.

We know that if $\phi$ is a root of P(x), then $1+\phi$ is a root of P(x-1). Since the roots of unity satisfy $x^n - 1 = 0$, then this new set of numbers $(1+\zeta^b)$ are the roots of $(x-1)^n - 1 = 0$, which by binomial theorem and vietas's formulas, we know the product of all the roots is 2, using the fact that n is odd.

On the other hand, for the general case gcd(a,n) = k, we know that every $\frac{n}{k}$ elements form a complete residue system modulo $\displaystyle \frac{n}{k}$, since the elements $ab$ repeat every $\frac{n}{k}$ elements, and since there cannot be smaller cycles and each cycle has $\frac{n}{k}$ elements of the $\frac{n}{k}$th roots of unity, we know that we will end up with a rearrangement of $(\prod \limits_{b=1}^{\frac{n}{k}}(1+\zeta^b))^k=2^k$, so we are done.

Answer 2

Since $\gcd(a,n)=k$, there exists $a',n'\in\mathbb{N}$ such that $a=a'k$ and $n=n'k$ and $\gcd(a',n')=1$. Therefore, for any $b\in\{1,2,\ldots,n\}$, we get $$\large\zeta^{ab}=e^{\frac{2\pi iab}{n}}=e^{\frac{2\pi ia'kb}{n'k}}=e^{\frac{2\pi ia'b}{n'}}$$ Therefore $\zeta^{ab}=1$ if and only if $b=jn'$ where $j\in\{1,2,\ldots,k\}$. If $n'=1$, the equality is trivial. So, assume $n'>1$. For $j\in\{1,2,\ldots,k\}$ we get $$\large\prod_{l=0}^{n'-1}\left(1+\zeta^{a(jn'+l)}\right)=\prod_{l=0}^{n'-1}\left(1+e^{\frac{2\pi ia(jn'+l)}{n}}\right)\\\large=\prod_{l=0}^{n'-1}\left(1+e^{\frac{2\pi ia'(jn'+l)}{n'}}\right)=\prod_{l=0}^{n'-1}\left(1+e^{\frac{2\pi il}{n'}}\right)\\\large=(-1)^{n'}((-1)^{n'-1}-1)=-(-1-1)=2$$ Since $n$ is odd then so is $n'$ and $\gcd(a',n')=1$, $e^{2\pi ia'/n'}$ is a primitive $n'$th root of unity. Hence the last two steps are true.

Therefore we get, $$\large\prod_{b=1}^{n}(1+\zeta^{ab})=\prod_{l=0}^{n'}\prod_{j=1}^{k}\left(1+\zeta^{a(jn'+l)}\right)\\\large=\prod_{j=1}^{k}\prod_{l=0}^{n'}\left(1+\zeta^{a(jn'+l)}\right)=\prod_{j=1}^{k}2=2^k$$ $$\tag*{$\square$}$$

Answer 3

Okay so we will use two facts:

FunFact 1: $\zeta^{cb}=\zeta^{ab}$ if $c\equiv a\pmod{n}$ where $\zeta$ is the $n^{th}$ root of unity.

FunFact 2: $\prod_{b=1}^n (1+\zeta^b)=2$ where $\zeta$ is the $n^{th}$ root of unity.

As, $\gcd(a,n)=k\implies a=kA, n=kN$ for some co-prime natural numbers $A$ and $N$. Thus, $$\zeta^{ab}=e^{\frac{2\pi i\cdot kAb}{kN}}=e^{\frac{2\pi iAb}{N}}=\xi^{Ab}$$where $\xi$ is the $N^{th}$ root of unity and $\gcd(A,N)=1$. Thus, from FunFact 1. we get $$\zeta^{ab}=\xi^{cb}$$where $A\equiv c\pmod{N}$ such that $0<c<N$. Also, $\gcd(A,N)=1\implies \gcd(c,N)=1$ and thus, $$\mathcal S:=\{bc\pmod{N}: b\in\mathbb N, 1\leq b\leq N\}$$forms a complete residue class modulo $N$. Thus, $$\prod_{b=1}^N(1+\zeta^{ab})=\prod_{b=1}^N(1+\xi^{cb})=\prod_{i=1}^N(1+\xi^{i})=2$$where the last equality follows from FunFact 2. Now, note that, from FunFact 1., we also know that $$\prod_{b=1}^{N}(1+\zeta^{ab})=\prod_{b=N+1}^{2N}(1+\zeta^{ab})=\cdots = \prod_{b=N(k-1)+1}^{kN}(1+\zeta^{ab})$$and thus, as $kN=n$, we have, $$\prod_{b=1}^{n}(1+\zeta^{ab})=\left(\prod_{b=1}^{N}(1+\zeta^{ab})\right)^k=2^k$$completing the proof.