Table of Contents
|
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:
- 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.