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)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:
- Without loss of generality, assume that $i > j$. Then $i - j > 0$ and so:
- 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$. |