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  a^{2}  a^{3}  a^{4}  a^{5}  a^{6} 

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, g^{2}, …, 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  a^{2}  a^{3}  a^{4}  a^{5}  a^{6} 

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)  3^{2} (mod 7)  3^{3} (mod 7)  3 ^{4} (mod 7)  3^{5} (mod 7)  3^{6} (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  a^{2}  a^{5}  a^{10} 

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 a^{k} (mod m) if and only if (k, t) = 1.
 Proof: Suppose that (k, t) = 1 and let s be the order of a^{k}. 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 a^{k}, 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 a^{k} has order t.
Theorem: Every prime p has Φ(p1) primitive roots.
 Proof: From theorem 2 we know that each integer in the set: $1, 2, 3, ..., p1$ has an order that is a divisor of $\phi (p) = p  1$. For each divisor of p1, we will let $\psi (t)$ be the number of integers in the set $1, 2, 3, ..., p1$ 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 a^{k} 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.