📂Number Theory

Proof of the Primitive Element Theorem

Definition ¹

If $1 \le a \le p$ satisfies $\text{ord}_{p} (a) = p-1$, it is defined as a primitive root modulo $p$.

---

• The order $\text{ord}_{p} (a)$ refers to the smallest natural number $e$ that satisfies $a^{e} \equiv 1 \pmod{p}$.

Theorem

Every prime number $p$ has $\phi ( p - 1)$ primitive roots.

---

• $\phi$ is the totient function.

Explanation

The reason why $a$ satisfying $\text{ord}_{p} (a) = p-1$ is called a primitive root is because, by Fermat’s little theorem, it is guaranteed that $a^{p-1} \equiv 1 \pmod{ p }$, so if exactly $\text{ord}_{p} (a) = p-1$, it means that all numbers between $1$ and $p$ can be represented by powers of $a$.

For example, consider the primitive root $a = 3$ of $p=7$ $$\begin{align*} 1 \equiv & 3^{0} \pmod{ 7 } \\ 2 \equiv & 3^{2} \pmod{ 7 } \\ 3 \equiv & 3^{1} \pmod{ 7 } \\ 4 \equiv & 3^{4} \pmod{ 7 } \\ 5 \equiv & 3^{5} \pmod{ 7 } \\ 6 \equiv & 3^{3} \pmod{ 7 } \end{align*}$$

Now focusing on $a$ for $p=7$, $$\begin{align*} 1^{1} \equiv & 1 \pmod{ 7 } \\ 2^{3} \equiv & 1 \pmod{ 7 } \\ 3^{6} \equiv & 1 \pmod{ 7 } \\ 4^{3} \equiv & 1 \pmod{ 7 } \\ 5^{6} \equiv & 1 \pmod{ 7 } \\ 6^{2} \equiv & 1 \pmod{ 7 } \end{align*}$$

Here, the number of primitive roots of $p=7$ is two, $3,5$, $$\phi (7-1) = \phi (6) = \phi (3) \phi (2) = (3-1)(2-1) = 2$$ which exactly matches. On the other hand, $\phi ( p - 1)$ is at least $1$, so it’s okay to use just for mentioning existence, not the exact number. This totient function $\phi$ might seem to appear out of nowhere but it is an essential element in the proof process.

Proof

Part 1.

According to the properties of order, for all $1 \le a \le (p-1)$, now for all divisors $d$ that divide $(p-1)$, let’s define the function $\psi$ as $$\psi ( d ) := \left| \left\{ a \ | \ 1 \le a < p \land \text{ord}_{p} (a) = d \right\} \right|$$ In Part 4, we will show that this $\psi$ is essentially the same function as the totient function $\phi$.

---

Part 2.

Let’s call the divisors that divide $(p-1)$ as $n$, then $(p-1) = nk$, and factoring out $\left( X^{p-1} - 1 \right)$ results in

$$\begin{align*} X^{p-1} - 1 =& X^{nk} - 1 \\ =& \left( X^{n} \right)^{k} - 1 \\ =& \left( X^{n} - 1 \right) \left( \left( X^{n} \right)^{k-1} + \left( X^{n} \right)^{k-2} + \cdots + \left( X^{n} \right)^{2} + \left( X^{n} \right)^{1} + 1 \right) \end{align*}$$

By Fermat’s little theorem, $$X^{p-1} - 1 \equiv 0 \pmod{p}$$ has $X=1,2,\cdots,(p-1)$ as a root, and by the fundamental theorem of algebra for congruences, $X^{n} -1 \equiv 0 \pmod{p}$ has at most $n$ roots therefore $$\left( X^{n} \right)^{k-1} + \left( X^{n} \right)^{k-2} + \cdots + \left( X^{n} \right)^{2} + \left( X^{n} \right)^{1} + 1 \equiv 0 \pmod{p}$$ has at most $n(k-1)$ roots. Thinking again about $$X^{p-1} - 1 \equiv \left( X^{n} - 1 \right) \left( \left( X^{n} \right)^{k-1} + \left( X^{n} \right)^{k-2} + \cdots + \left( X^{n} \right)^{2} + \left( X^{n} \right)^{1} + 1 \right) \pmod{p}$$

• The left side has exactly $(p-1) = nk$ roots
• The right side has at most $n$ roots and at most $n(k-1)$ roots.

To satisfy this, $X^{n} -1 \equiv 0 \pmod{p}$ must have at least, that is, exactly $n$ roots. In summary, if $n | (p-1)$ then $$X^{n} -1 \equiv 0 \pmod{p}$$ has exactly $n$ solutions in $0 \le X < p$.

---

Part 3. $\displaystyle \sum_{i=1}^{r} \psi (d_{i}) = n$

Let’s denote all divisors of $n$ as $d_{1} , \cdots , d_{r}$.

If the divisor $d$ of $n$ satisfies $d = \text{ord}_{p} (a)$, then from the definition of order $$a^{d} = a^{\text{ord}_{p} (a)} \equiv 1 \pmod{p}$$ is obtained. Here, the number of $a$ satisfying the given $d$ is $\psi (d)$.

However, since $$a^{n} \equiv a^{d \cdot \left( {{n} \over {d}} \right)} \equiv 1^{ \left( {{n} \over {d}} \right)} \equiv 1 \pmod{p}$$ Thus, $\psi (d)$ of $X = a$ becomes a solution of $X^{n} -1 \equiv 0 \pmod{p}$.

Summarizing, the number of solutions of $X^{n} -1 \equiv 0 \pmod{p}$ is $$\sum_{d \mid n} \psi (d) = \psi (d_{1} ) + \psi (d_{2} ) + \cdots + \psi (d_{r} )$$ Since we stated in Part 2 that the number of solutions of $X^{n} -1 \equiv 0 \pmod{p}$ is $n$, $$\sum_{d \mid n} \psi (d) = \psi (d_{1} ) + \psi (d_{2} ) + \cdots + \psi (d_{r} ) = n$$ This is similar to the totient sum formula.

---

Part 4. $\phi (n) = \psi (n)$

We need to show that for all natural numbers $n$, $\phi (n) = \psi (n)$ holds true.

Calculations for $\psi$ are obtained using $\displaystyle \sum_{i=1}^{r} \psi (d_{i}) = n$ unless otherwise mentioned.

• Case 1. $n=1$
  $\phi (1) = 1$ and $\psi (1) = 1$, therefore $$\phi (1) = \psi (1)$$
• Case 2. For prime $q$ when $n=q$
  $\phi (q) = q - 1$ and $\psi (q) + \psi (1) = q$, therefore $$\phi (q) = q - 1 = \psi (q)$$
• Case 3. For prime $q$ when $n=q^2$
  The divisor of $q^2$ is only $1, q, q^2$, hence $$\phi (q^2) + \phi (q) + 1 = q^{2} = \psi (q^2) + \psi (q) + 1$$ After subtracting the terms for Case 1 and 2 from both sides, $$\phi (q^2) = \psi (q^2)$$
• Case 4. For different primes $q_{1}, q_{2}$ when $n=q_{1} q_{2}$
  The divisor of $q_{1} q_{2}$ is only $1, q_{1}, q_{2}, q_{1} q_{2}$, hence $$\phi ( q_{1} q_{2}) + \phi (q_{1}) + \phi (q_{2}) + 1 = q_{1} q_{2} = \psi ( q_{1} q_{2}) + \psi (q_{1} ) + \psi (q_{2} ) + 1$$ After subtracting the terms for Case 1 and 2 from both sides, $$\phi ( q_{1} q_{2} ) = \psi ( q_{1} q_{2} )$$
• Otherwise.
  In other cases, by breaking down the terms as in Cases 3 and 4, we obtain $\phi (n) = \psi (n)$.

---

Part 5.

In Parts 2 and 3, we confirmed that for all $n$ satisfying $n | (p-1)$, there are $\phi (n)$ number of $a$ satisfying $\text{ord}_{p} (a) = n$. Here, if $k=1$, that is, $n = p-1$, then $\text{ord}_{p} (a) = p-1$, hence $a$ is a primitive root modulo $p$. Therefore, prime number $p$ has $\phi (p-1)$ primitive roots.

■