Show that 5 is a primitive root modulo 49.
We remind ourselves of Definition (6.10) which states that if $a \pmod n$ has order $\phi (n)$ then $a$ is called a primitive root modulo $n$ or just a primitive root of $n$.
We first note that $\gcd(5,49)=1$ and so the order exists. The order is a factor of $\phi(49)=42$. These factors are 1, 2, 3, 6, 7, 14, 21, 42, and are the only ones we need to test.
The following calculations show the order of $5 \pmod {49}$ is not 2, 3, 6, 7 or 14.
| n | 5^n | 5^n mod 49 |
| 2 | 25 | 25 |
| 3 | 125 | 27 |
| 6 | 15625 | 43 |
| 7 | 78125 | 19 |
| 14 | 6103515625 | 18 |
The numbers grow too large for factors 21 and 42, so we use an indirect calculation.
For factor 21,
$$ 5^{21} \equiv (5^7)^3 \equiv 19^3 \equiv 6859 \equiv 48 \pmod {49} $$
For factor 42,
$$ 5^{42} \equiv (5^{14})^3 \equiv 18^3 \equiv 6832 \equiv 1 \pmod {49} $$
And so the order of 5 modulo 49 is 42.
Because the order is $\phi(49)=42$, we conclude that 5 is a primitive root modulo 49.