Primitive Root

Let $n$ be an positive integer. Then integer $a$ is said to be a Primitive Root of $n$ (if it exist), if

$\text{ord} _{n} a = \phi (n)$

Existence

Primitive roots only exist for certain integers. In fact, it only exist for $n=2,4, p^t$ or $2p^t$ , where $p$ is a ODD prime and $t$ is a positive integer.

The proof of that statement is extremely long and tedious. Euler tried to prove it but his proof was wrong. This is a link to the proof: Proof of the Existence of Primitive Roots

How to Find a Primitive Root

Once you find a primitive root for a prime number $p$ (which you probably just have to find by trial and error), $r$ , determine if

$r^{p-1} \equiv 1 \pmod {p^2}$

If $r^{p-1} \equiv 1 \pmod {p^2}$ , then $r$ is not a primitive root of $p^2$ , but $r+p$ is. Now, $r^{p-1} \equiv 1 \pmod {p^2}$ is extremely rare, so for the vast majority of the time, if $r$ is a primitive root for $p$ , it is also a primitive root of $p^2$ . However, if $r+p$ is a primitive root of $p^2$ , then obviously $r+p$ is also a primitive root of $p$ . Now, if $r$ is a primitive root of both $p$ and $p^2$ , then $r$ is a primitive root of $p^k$ for all positive integers $k$ .