# Adding primitive $n^\text{th}$ roots of unity, where $n$ is not square-free.

I want to show that, for $n$ not square-free, $$\sum\limits_{\substack{1\leq k \leq n\\ \gcd(k,n)=1}} \xi _n^k=0,$$ where $\xi_n$ is a (fixed) primitive $n^\text{th}$ root of unity (in $\mathbb C$).

I vaguely recall someone showing me that this can be done by multiplying the sum by a suitable element $\neq 1$ and then show that you are left with the same sum.

If you know some other method, I would like to know as well. However, I want to avoid using the Möbius function.

For any $k$ such that $\gcd(k,n)=1$, we are just summing the primitive $n$-th roots of unity, i.e. the roots of the cyclotomic polynomial $\Phi_n(x)$. By invoking Viète's theorem, we just have to prove that if $n$ is not squarefree, the coefficient of $x^{\varphi(n)-1}$ in $\Phi_n(x)$ is zero. Since $\Phi_n(x)$ is a palindromic polynomial, that is the same as proving that the derivative of $\Phi_n(x)$ at $x=0$ is zero.

By Möbius formula (I wrote this answer before the OP modified his question): $$\Phi_n(x) = \prod_{d\mid n}\left(x^{\frac{n}{d}}-1\right)^{\mu(d)} \tag{1}$$ hence by taking the logarithmic derivative: $$\frac{\Phi_n'(x)}{\Phi_n(x)}=\sum_{d\mid n}\mu(d)\frac{n}{d}\cdot \frac{x^{\frac{n}{d}-1}}{x^{\frac{n}{d}}-1}\tag{2}$$ and taking the limit as $x\to 0$ (just one term of the last sum does not vanish) we get: $$\frac{\Phi_n'(0)}{\Phi_n(0)} = -\mu(n). \tag{3}$$

• I am very sorry for not saying this explicitely in the OP, but I want to avoid the Möbius function. I will edit this right away. Dec 8, 2015 at 15:29
• @gebruiker: all right, done. Dec 9, 2015 at 10:33

We want to multiply the sum by $\zeta_n^{\nu}$ with $0 < \nu < n$, so that $\zeta_n^{\nu} \neq 1$, and we need

$$\gcd (k,n) = 1 \iff \gcd (k+\nu,n) = 1\tag{1}$$

to conclude

$$\sum_{\substack{1 \leqslant k \leqslant n \\ \gcd (k,n) = 1}} \zeta_n^k = \sum_{\substack{1 \leqslant k \leqslant n \\ \gcd (k,n) = 1}} \zeta_n^{k+\nu}\tag{2}$$

since both sums then contain the same terms.

With

$$\nu = \operatorname{rad} (n) := \prod_{p \mid n} p,$$

we have $(1)$, for then $p \mid \gcd(k,n) \iff p \mid \gcd (k+\nu,n)$. We thus have

$$0 = (1 - \zeta_n^{\operatorname{rad} (n)})\sum_{\substack{1 \leqslant k \leqslant n \\ \gcd (k,n) = 1}} \zeta_n^k\tag{3}$$

for every $n$. Since $\operatorname{rad} (n) < n$ if and only if $n$ is not squarefree, $(3)$ implies

$$\sum_{\substack{1 \leqslant k \leqslant n \\ \gcd(k,n) = 1}} \zeta_n^k = 0$$

for $n$ that are not squarefree, as $1 - \zeta_n^{\operatorname{rad} (n)} \neq 0$ in that case.