Exercise 4.10

Proof. Notation: ${𝔽}_p=\mathbb{Z}∕\mathit{p\mathbb{Z}}$ is the field with $p$ elements, $|x|$ the multiplicative order of an element $x\in {𝔽}_p^{\text{∗}}$, ${\mathbb{N}}^{\text{∗}}=\{1,2,3,\dots \}$.

Let

so that $\psi (n)$ is the sum of the elements with order $n$ in ${𝔽}_p^{\text{∗}}$. So $\psi (n)=0$ if $n\nmid p-1$, and $S=\psi (p-1)$ is the sought sum of all the primitive roots modulo $p$.

We compute for all $n\in {\mathbb{N}}^{\text{∗}}$

$f(n)$ is the sum of elements whose order divides $n$, in other worlds the sum of the roots of $x^n-1$. This sum is, up to the sign, the coefficient of $x^{n-1}$, so is null, except in the case $n=1$, where the sum of the unique root $1$ of $x-1$ is $1$. So

( $f={\chi }_{\{1\}}$ is the characteristic function of $\{1\}$).

From the Möbius inversion formula, for all $n\in {\mathbb{N}}^{\text{∗}},\psi (n)={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{d\mid m}\mu \left(\frac{n}{d}\right)f(d)$, so

Conclusion :

the sum of all the primitive roots modulo $p$ is congruent to $\mu (p-1)$ modulo $p$. □