# Find the sum of all primitive roots of $n$

Let $\xi_n$ denote a primitive $n^{th}$ root of unity and let $K=\mathbb{Q}(\xi)$ be the associated cyclotomic field. Let $a$ denote the trace of $\xi_n$ from $K$ to $\mathbb{Q}$. Prove that $a=1$ if $n=1$, $a=0$ if $n$ is divisible by the square of a prime, and $a=(-1)^r$ if $n$ is the product of $r$ distinct primes. It is actually the

I know that the trace of $\xi_n$ from $K$ to $\mathbb{Q}$ is the sum of all primitive roots of $n$.

If $n=1$, it is very easy.

I know the fact that $a$ is a primitive root of $n$, then $-a$ is a primitive of $n$ as well if $n$ is divisible by the square of a prime. How to prove that? This is the key to prove the second case.

For the third case, I totally had no idea.

How to prove the two cases using theorems about the cyclotomic field or cyclotomic polynomial?

It can be shown that if $F$ and $F^\star$ are defined by :

$$F(n)=\sum_{k=1}^n f\left(\frac kn\right)\quad\mathrm{and}\quad F^\star(n)=\sum_{\matrix{1\le k\le n\cr gcd(k,n)=1}}f\left(\frac kn\right)$$

then, for all $n\ge 1$ :

$$F(n)=\sum_{d\mid n}F^\star(d)$$

Mobius inversion formula then gives :

$$F^\star(n)=\sum_{d\mid n}\mu(d)F\left(\frac nd\right)$$

Now, taking $f(t)=e^{2i\pi t}$ leads to :

$$F(n)=\sum_{k=1}^ne^{2ik\pi/n}=\left\{\matrix{1\ & \mathrm{if }\,\,n=1\cr 0 & \mathrm{if}\,\,n\ge1}\right.$$

Hence :

$$\sum_{\matrix{1\le k\le n\cr gcd(k,n)=1}}e^{2ik\pi/n}=\mu(n)$$

• Can we use the cyclotomic field or cyclotomic polynomial to prove it? – User90 Apr 10 '17 at 23:37
• Yes. The trace is the negative of the coeff. of the second-leading power of $x$ in the minimal polynomial. Write $\Phi_n(x)$ for the $n$th cyclotomic polynomial. You want that coeff. to be $-\mu(n)$. Use Moebius inversion on the identity $x^n - 1 = \prod_{d|n} \Phi_d(x)$ for all $n \geq 1$ we get $\Phi_n(x) = \prod_{d|n} (x^d-1)^{\mu(n/d)}$ for all $n \geq 1$. Use this to figure out the coefficient of $x^{\varphi(n)-1}$ in $\Phi_n(x)$. Or by symmetry of coefficients for $n > 1$, figure out the linear coefficient of $x$ in $\Phi_n(x)$ by that formula (hint: look at the formula modulo $x^2$). – KCd Apr 10 '17 at 23:53