The Primitive Roots of a Natural Number

# The Primitive Roots of a Natural Number

Recall from The Order of a Natural Number Modulo m page that if $a, m \in \mathbb{N}$ then the order of $a$ modulo $m$ is the least positive integer $t$ such that:

(1)
\begin{align} \quad a^t \equiv 1 \pmod m \end{align}

We noted that if $(a, m) = 1$ then the order of $t$ is well defined and $1 \leq t \leq \phi (m)$.

We will now look at another important notion called a primitive root.

 Definition: Let $a, m \in \mathbb{N}$ and let $a$ be a least residue modulo $m$. $a$ is said to be a Primitive Root of $m$ if the order of $a$ is $\phi (m)$.

For example, let $m = 7$ and consider the following table of $a, a^2, ..., a^6$ modulo $7$ where $a = 1, 2, ..., 6$:

a a2 a3 a4 a5 a6
1 1 1 1 1 1
2 4 1 2 4 1
3 2 6 4 5 1
4 2 1 4 2 1
5 4 6 2 3 1
6 1 6 1 6 1

Note that since $7$ is prime we have that $\phi (7) = 6$. Furthermore, the only least residues modulo $7$ with order $\phi(7) = 6$ are $a = 3$ and $a = 5$ - which are the primitive roots of $7$ to which there are $2$.

We will now look at a very nice theorem regarding primitive roots which tells us that if $a$ is a primitive root of $m$ then all of the powers of $a$ up to $a^{\phi(m)}$ give us a permutation of all $\phi (m)$ natural numbers that are relatively prime to $m$.

 Theorem 1: Let $a, m \in \mathbb{N}$ and let $(a, m) = 1$. If $a$ is a primitive root of $m$ then the least residues of $a, a^2, ..., a^{\phi(m)}$ are a permutation of the $\phi (m)$ natural numbers that are relatively prime to $m$.
• Proof: Since $(a, m) = 1$ we see that $(a^i, m) = 1$ for all $i$ with $1 \leq i \leq m$. We want to show that no two powers of $a$ have the same least residue modulo $m$. Suppose otherwise, i.e., suppose that for $i, j \in \{ 1, 2, ..., \phi (m) \}$ with $i \neq j$ we have:
(2)
\begin{align} \quad a^i \equiv a^j \pmod m \end{align}
• Without loss of generality, assume that $i > j$. Then $i - j > 0$ and so:
(3)
\begin{align} \quad a^{i - j} \equiv 1 \pmod m \end{align}
• But then the order of $a$ is less than $i - j$. But $i - j \leq \phi (m)$ which contradicts $a$ being a primitive root of $m$. So the assumption that $a^i \equiv a^j \pmod m$ for distinct $i, j \in \{ 1, 2, ..., \phi (m) \}$ is false. I.e., the least residues of $a, a^2, ..., a^{\phi(m)}$ are all distinct. Hence there are $\phi (m)$ many elements of the least residues of $a, a^2, ..., a^{\phi(m)}$.
• So there are $\phi(m)$ many elements $a^i$ with $(a^i, m) = 1$, so the least residues of $a^1, a^2, ..., a^{\phi(m)}$ modulo $m$ are a permutation of the $\phi (m)$ positive integers that are relatively prime to $m$. $\blacksquare$
 Theorem 2: Let $a, m \in \mathbb{N}$ and let $t$ be the order of $a$ modulo $m$. Then $t$ is also the order of $a^k$ modulo $m$ if and only if $(k, t) = 1$.