Determining the Number of Primitive Roots a Prime Has

We know that any prime p has $\phi (p - 1)$ primitive roots. We also know that the prime power decomposition of p - 1 can be written as: $p - 1 = p_1^{e_1}p_2^{e_2}...p_k^{e_k}$, and we then know that $\phi (p - 1) = p_1^{e_1 - 1}(p_1 - 1)p_2^{e_2 - 1}(p_2 - 1) ... p_k^{e_k - 1}(p_k - 1)$.

We hence have everything we need to calculate the number of primitive roots that a prime has.

Example 1

Determine how many primitive roots the prime 37 has.

From the property we derived above, 37 should have $\phi (37-1) = \phi (36)$ primitive roots. All we need to do know is calculate $\phi (36)$:

(1)

\begin{align} \phi (36) = \phi (2^2) \phi (3^2) \\ \phi (36) = 2^{2-1} (2-1) 3^{2-1} (3-1) \\ \phi (36) = (2)(1)(3)(2) \\ \phi (36) = 12 \end{align}

Hence 37 has 12 primitive roots.

Example 2

Determine how many primitive roots the prime 1321 has.

Once again, we need to calculate $\phi (1321-1) = \phi (1320)$:

(2)

\begin{align} \phi (1320) = \phi (2^3) \phi (3) \phi (5) \phi (11) \\ \phi (1320) = (4)(2)(4)(10) \\ \phi (1320) = 320 \end{align}

Hence, 1321 has 320 primitive roots.