Primitive Roots

# Primitive Roots

 Definition: If a is a least residue (mod m), and the order of a (mod m) is $\phi (m)$, then a is said to be a primitive root of m.

Let's construct a table of showing $a^n \pmod 7$, where a = 1, a = 2, …, a = 6. We thus obtain:

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

We know that $\phi (7) = 6$. Hence any of the least residues (mod 7) with order 6 are primitive roots. In fact, 3 and 5 are primitive roots of 7, since the order of 3 (mod 7) is $\phi (7)$, and the order of 5 (mod 7) is $\phi (7)$.

## Theorem 1: If g is a primitive root of m, then the least residues of g, g2, …, gΦ(m) (mod m) are a permutation of the Φ(m) positive integers relatively prime to m.

• Proof: $(g, m) = 1$, and each power of g is relatively prime to m, that is $(g^i, m) = 1$ for 1 ≤ i ≤ Φ(m). Also, no two powers have the same least residue, that is if 1 ≤ r ≤ Φ(m) and 1 ≤ s ≤ Φ(m), r ≠ s, then if $r \equiv s \pmod {\phi (m)}$ implies $g^r \equiv g^s \pmod m$. This cannot be true though, so $r \not\equiv s \pmod {\phi (m)}$.

### Example 2

Verify theorem 1 with knowing that 3 is a primitive root of 7.

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

From the table above, we should note that the horizontal row across the primitive roots contain all $\phi (m)$ least residues (mod 7). In fact, these are the only two rows with this property. Let's verify this visually. 3 is a primitive root of 7, so:

3 (mod 7) 32 (mod 7) 33 (mod 7) 3 4 (mod 7) 35 (mod 7) 36 (mod 7)
3 2 6 4 5 1

Once again their are $\phi (7) = 6$ distinct numbers relatively prime to 7. (3, 7) = 1, (2, 7) = 1, (6, 7) = 1, (4, 7) = 1, (5, 7) = 1, (1, 1) = 1.

### Example 3

Find a primitive root of 11.

We know 1, 2, 3, …, 10 has an order t that is a divisor of $\phi (11) = 10$. The only divisors of 10 are 1, 2, 5, and 10. Setting up a table we obtain:

a a2 a5 a10
1 1 1 1
2 4 10 1
3 9 1 1
4 5 1 1
5 3 1 1
6 3 10 1
7 5 10 1
8 9 10 1
9 4 1 1
10 1 10 1

From the construction of our table, we see that 2, 6, 7, and 8 are all primitive roots of 11 since 2, 6, 7, and 8 have order $\phi (11) = 10$.

## Lemma 1: If t is the order of a (mod m), then t is the order of ak (mod m) if and only if (k, t) = 1.

• Proof: Suppose that (k, t) = 1 and let s be the order of ak. We have that $1 \equiv (a^t)^k \equiv (a^k)^t \pmod m$. Since $(a^k)^t \equiv 1 \pmod m$, then it follows that since s is the order of ak, then s | t. Now we also know that $(a^k)^s \equiv a^{ks} \equiv 1 \pmod m$, so t | ks as well. Since (k, t) = 1, it follows by an early corollary that t | s. Since s | t and t | s, then s = t, and so ak has order t.

# Theorem: Every prime p has Φ(p-1) primitive roots.

• Proof: From theorem 2 we know that each integer in the set: $1, 2, 3, ..., p-1$ has an order that is a divisor of $\phi (p) = p - 1$. For each divisor of p-1, we will let $\psi (t)$ be the number of integers in the set $1, 2, 3, ..., p-1$ that have order t. Hence:
(1)
\begin{align} \sum_{t \: | \: p - 1} \psi (t) = p - 1 = \sum_{t \: | \: p - 1} \phi (t) \end{align}
• We now want to show that $\psi (t) = \phi (t)$. We will do this by showing that $\psi (t) ≤ \phi (t)$, $\forall t$. First let's choose some t. If $\psi (t) = 0$, then it follows that $\psi (t) < \phi (t)$. If $\psi (t) ≠ 0$, then there exists an integer b that has order t. Hence $x^t \equiv 1 \pmod p$ has t solutions, and is satisfied by the integers $b, b^2, b^3, ..., b^t$. None of these have the same least residue (mod p), so they give all solutions. But by lemma 1, $b, b^2, b^3, ..., b^t$ have the powers of ak such that $(k, t) = 1$. There are $\phi ( t)$ of these numbers, so $\psi (t) = \phi (t)$.

## Corollary 1: If t | Φ(p) , then the number of least residues (mod p) that have order t is Φ(t).

We will not prove this corollary, however we will verify its truth from the original example. From the original example on the top of this page, 2 and 4 have order 3 (mod 7). Our prime p, 7, subtract 1 is equal to 6. Clearly 2 | 6, so the number of least residues (mod 7) that have order 3 will be $\phi (3) = 2$, which is true.