# 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)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)Hence, 1321 has 320 primitive roots.