Show that 2 is a primitive root modulo 9.
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(2,9)=1$ and so the order exists. The order is a factor of $\phi(9)=6$. These factors are 1, 2, 3, 6, and are the only ones we need to test.
The following calculations show the order of $2 \pmod 9$ is 6.
| n | 2^n | 2^n mod 9 |
| 2 | 4 | 4 |
| 3 | 8 | 8 |
| 6 | 64 | 1 |
Because the order is $\phi(9)=6$, we conclude that 2 is a primitive root modulo 9.