Exercise 4.3.29* (The sum $S$ of all the primitive roots modulo $p$ satisfies $S \equiv \mu(p-1) \pmod p$)

Proof.

(a)

As usual, we write ${𝔽}_p$ the field $\mathbb{Z}∕\mathit{p\mathbb{Z}}$ with $p$ elements, and if $a\in \mathbb{Z}$, we write ${[a]}_p$ (or $\bar{a}$ if $p$ is fixed) the class of $a$ in $\mathbb{Z}∕\mathit{p\mathbb{Z}}$. If $P$ is a (formal) polynomial, we write indifferently $P$ or $P(x)$ this polynomial.

Let ${\mathrm{\Psi }}_n(x)\in {𝔽}_p[x]$ denote the monic polynomial with coefficients in ${𝔽}_p$ whose roots are the elements of ${𝔽}_p^{\text{∗}}$ of order $n$:

$${\mathrm{\Psi }}_n(x)=\underset{a\in {𝔽}_p^{\text{∗}},\mathrm{ord}(a)=n}{\prod }(x-a).$$

By Fermat’s Theorem, $a^{p-1}=\bar{1}$ for all $a\in {𝔽}_p^{\text{∗}}$, therefore the order of any element of ${𝔽}_p^{\text{∗}}$ divides $p-1$, so the product in the right member is empty if $n\nmid p-1$ and then ${\mathrm{\Psi }}_n(x)=\bar{1}$.

(For instance, if $p=13$, then the elements of order 12 in ${𝔽}_{13}$ are $\pm \bar{2},\pm \bar{6}$, so ${\mathrm{\Psi }}_{12}(x)=(x+\bar{2})(x-\bar{2})(x+\bar{6})(x-\bar{6})=(x^2-\bar{4})(x^2+\bar{3})=x^4-x+\bar{1}$, and ${\Phi }_{12}(x)=x^4-x+1$; chance and coincidences ...)

First, with the same proof as in Problem 26, we show by “copy and paste” that

$$\underset{d\mid p-1}{\prod }{\mathrm{\Psi }}_d(x)=x^{p-1}-\bar{1}.$$

By definition, for every divisor $d$ of $n$,

$${\mathrm{\Psi }}_d(x)=\underset{a\in A_d}{\prod }(x-a),$$

where $A_d$ is the subset of ${𝔽}_p^{\text{∗}}$ of the elements of order $d$ in the group $({𝔽}_p^{\text{∗}},\times )$:

$$A_d=\{a\in {𝔽}_p^{\text{∗}}\mid \mathrm{ord}(a)=d\}.$$

Since the order of every element of ${𝔽}_p^{\text{∗}}$ divides $p-1$,

$${𝔽}_p^{\text{∗}}=\underset{d\mid p-1}{\bigcup }{A}_d\text{(disjoint union)}.$$

Therefore

$$\begin{array}{llll}\hfill x^{p-1}-\bar{1}& =\underset{a\in {𝔽}_p^{\text{∗}}}{\prod }(x-a)& \hfill & \\ \hfill & =\underset{d\mid p-1}{\prod }\underset{a\in A_d}{\prod }(x-a)& \hfill & \\ \hfill & =\underset{d\mid n}{\prod }{\mathrm{\Psi }}_d(x).& \hfill & \end{array}$$

This shows that

$$\begin{array}{lll}\hfill x^{p-1}-\bar{1}=\underset{d\mid n}{\prod }{\mathrm{\Psi }}_d(x).& & \hfill \text{(1)}\end{array}$$

Next, consider the map

$$\phi \{\begin{array}{ccc}\hfill \mathbb{Z}[x]\hfill & \hfill \to \hfill & {𝔽}_p[x]\hfill \\ \hfill p(x)=\underset{i=0}{\overset{n}{\sum }}{a}_i{x}^i\hfill & \hfill \mapsto \hfill & \bar{p}(x)=\underset{i=0}{\overset{n}{\sum }}\overline{a_i}{x}^i,\hfill \end{array}$$

where each coefficient of $p$ is replaced in $\bar{p}$ by its class modulo $p$.

Then $\phi$ is a ring homomorphism (i.e. for all polynomials $p,q$ in $\mathbb{Z}[x]$, $\phi (p+q)=\phi (p)+\phi (q),\phi (\mathit{pq})=\phi (p)\phi (q)$ and $\phi (1)=\bar{1}$).

We prove by strong induction that $\phi ({\Phi }_d)={\mathrm{\Psi }}_d$ for every divisor $d$ of $p-1$.

First, $\bar{1}$ is the only element with order $1$, so ${\mathrm{\Psi }}_1(x)=x-\bar{1}=\phi (x-1)=\phi ({\Phi }_1(x)).$

Suppose now that $n$ is a divisor of $p-1$, and that $\phi ({\Phi }_d)={\mathrm{\Psi }}_d$ is true for every divisor of $n$ less that $n$. Then by (1) and the induction hypothesis,

$$\begin{array}{llll}\hfill \phi (x^{p-1}-1)& =x^{p-1}-\bar{1}& \hfill & \\ \hfill & ={\mathrm{\Psi }}_n(x)\underset{d\mid n,d<n}{\prod }{\mathrm{\Psi }}_d(x)& \hfill & \\ \hfill & ={\mathrm{\Psi }}_n(x)\underset{d\mid n,d<n}{\prod }\phi ({\Phi }_d(x)),& \hfill & \end{array}$$

so

$$\begin{array}{lll}\hfill \phi (x^{p-1}-1)& ={\mathrm{\Psi }}_n(x)\underset{d\mid n,d<n}{\prod }\phi ({\Phi }_d(x)).& \hfill \text{(2)}\end{array}$$

Moreover, by Problem 26, $x^n-1={\prod <!--\; FUNCTION\; APPLICATION\; -->}_{d\mid n}{\Phi }_d(x)$, and $\phi$ is a ring homomorphism, so

$$\begin{array}{lll}\hfill \phi (x^{p-1}-1)& =\phi ({\Phi }_n(x))\underset{d\mid n,d<n}{\prod }\phi ({\Phi }_d(x)).& \hfill \text{(3)}\end{array}$$

Since $x^{p-1}-\bar{1}\ne 0$, we have ${\prod <!--\; FUNCTION\; APPLICATION\; -->}_{d\mid n,d<n}\phi ({\Phi }_d(x))\ne 0$. Since ${𝔽}_p$ is a field, ${𝔽}_p[x]$ is an integral domain, so the comparison of (2) and (3) gives $\phi ({\Phi }_n(x))={\mathrm{\Psi }}_n(x)$, and the induction is done.

In conclusion, for all divisors $d$ of $p-1$,

$$\begin{array}{lll}\hfill \phi ({\Phi }_d(x))={\mathrm{\Psi }}_d(x).& & \hfill \text{(4)}\end{array}$$

In the particular case $d=p-1$, as in the preceding example, $\phi ({\Phi }_{p-1}(x))={\mathrm{\Psi }}_{p-1}(x)$. The roots of ${\mathrm{\Psi }}_{p-1}(x)$ are the elements of ${𝔽}_p^{\text{∗}}$ of order $p-1$, so they are the primitive roots of unity in ${𝔽}_p^{\text{∗}}$.

An integer $g$ is a solution of the congruence ${\Phi }_{p-1}(x)\equiv 0(\mathit{mod}p)$ if and only if $0=\overline{{\Phi }_{p-1}}(\bar{g})=\phi ({\Phi }_{p-1})(\bar{g})={\mathrm{\Psi }}_{p-1}(\bar{g})$. Since the roots of ${\mathrm{\Psi }}_{p-1}(x)$ are the primitive roots in ${𝔽}_p^{\text{∗}}$, we can conclude:

An integer $g$ is a solution of the congruence ${\Phi }_{p-1}(x)\equiv 0(\mathit{mod}p)$ if and only if $g$ is a primitive root modulo $p$.

(b)

Since the primitive roots in ${𝔽}_p^{\text{∗}}$ (the elements of order $p-1$ in ${𝔽}_p^{\text{∗}}$) are the roots of ${\mathrm{\Psi }}_{p-1}=\phi ({\Phi }_{p-1})$, the sum of these primitive roots is the opposite of the coefficent of $x^{p-2}$ in ${\mathrm{\Psi }}_{p-1}(x)$.

By Problem 26, we know that the coefficient ${\sigma }_1$ of $x^{p-2}$ is $\mu (p-1)$, so

$${\Phi }_{p-1}(x)=x^{p-1}-\mu (p-1)x^{p-2}+r(x),\mathrm{deg}<!--\; FUNCTION\; APPLICATION\; -->(r)<p-2.$$

So

$${\mathrm{\Psi }}_{p-1}(x)=x^{p-1}-\overline{\mu (p-1)}{x}^{p-2}+\bar{r}(x),\mathrm{deg}<!--\; FUNCTION\; APPLICATION\; -->(\bar{r})<p-2.$$

Therefore

$$\underset{\gamma \in {𝔽}_p^{\text{∗}},\mathrm{ord}(\gamma )=p-1}{\sum }\gamma =\overline{\mu (p-1)}.$$

If $g_1,g_2,\dots ,g_{\phi (p-1)}$ are the primitive roots modulo $p$ in $[[1,p-1[[$, then $\overline{g_1},\overline{g_2},\dots ,\overline{g_{\phi (p-1)}}$ are the elements of order $p-1$ in ${𝔽}_p^{\text{∗}}$, thus $\overline{g_1}+\overline{g_2}+\cdots +\overline{g_{\phi (p-1)}}=\overline{\mu (p-1)}$, so

$$g_1+g_2+\cdots +g_{\phi (p-1)}\equiv \mu (p-1)(\mathit{mod}p).$$

The sum $S$ of all the primitive roots modulo $p$ satisfies $S\equiv \mu (p-1)(\mathit{mod}p)$.