Primitive root theorem. Let p be a prime. Then for any d dividing \( p-1 \), there are exactly \( \phi(d) \) elements of order d in \( (\mathbb Z / p \mathbb Z)^\times \). In particular there are \( \phi(p-1) \) primitive roots mod p.
Proof.
- \( H_m \): For any \( d_i \leq m \) dividing \( p-1 \), there are exactly \( \phi(d_i) \) elements of order \( d_i \) in \( (\mathbb Z / p \mathbb Z)^\times \).
- \( H_1 \): Only positive divisor of \( p-1 \) less than 1 is 1. \( H_1 \) is obviously true.
- \( H_k \): Assume \( H_m \) holds for some positive integer k.
- \( H_{k+1} \):
- \( k+1 \) doesn’t divide \( p-1 \). Then \( H_{k+1} \) is true since \( H_k \) is true.
- \( k+1 \) divides \( p-1 \). Based on \( H_k \), for any
\( d_i < k+1 \) dividing \( p-1 \),
there are exactly \( \phi(d_i) \) elements of order \( d_i \) in \( (\mathbb Z / p \mathbb
Z)^\times \).\( k+1=d^* \) divides \( p-1 \). \( x^{d^*}=1 \) has \( d^* \) distinct roots mod p.
Clearly the order of the roots must divide \( d^* \).
\begin{equation} d^{*}-\sum_{q | d^{*}, q<d^*} \phi(q)=\phi(d^{*}) \end{equation}
So there are exactly \( \phi(k+1) \) elements of order \( k+1 \) in \( (\mathbb Z / p \mathbb Z)^\times \).
Overall, \( H_{k+1} \) is true.
- Based on M.I., \( H_m \) is true.
◻︎
PREVIOUSFundamental Theorem of Algebra