Chapter 9

Primitive Roots

9.1 The multiplicative group of a finite field

Theorem 9.1. The multiplicative group F × of a finite field is cyclic.

Remark: In particular, if p is a prime then (Z/p)× is cyclic.

In fact, this is the only case we are interested in. But since the proof
works equally well for any finite field we prove the more general result.
Proof. The exponent of a finite group G is the smallest number e > 0 such
that
ge = e
for all g ∈ G.
By Lagrange’s Theorem, if G is of order n

gn = e

for all g ∈ G. Hence e ≤ n.

In fact it is easy to see that e | n. For suppose d = gcd(e, n). Then

d = er + ns.

It follows that
g d = (g e )r (g n )s = e.
We assume in the rest of the proof that F is a finite field, containing q
elements.
Lemma 9.1. The exponent of F × is q − 1.

9–1
9.1. THE MULTIPLICATIVE GROUP
CHAPTER
OF A FINITE
9. PRIMITIVE
FIELD ROOTS

Proof. Each of the q − 1 elements x ∈ F × (ie all the elements of F except 0)

satisfies the equation
xe − 1 = 0
over the field F .
But this equation has at most e roots. It follows that

q − 1 ≤ e.

Since e | q − 1 it follows that

e = q − 1.

Lemma 9.2. If A is a finite abelian group, and a, b ∈ A have coprime orders

r, s then
order(ab) = rs.
Proof. Suppose order(ab) = n. Then

(ab)rs = 1 =⇒ n | rs.

On the other hand, since r, s are coprime we can find x, y ∈ Z such that

rx + sy = 1.

But then
(ab)sy = asy = a1−rx = a.
It follows that r | n. Similarly s | n. Since gcd(r, s) = 1 this implies that

rs | n.

Hence
n = rs.

Lemma 9.3. Suppose A is a finite abelian group of exponent e. Then A has

an element of order e.

09-2317 9–2
9.2. PRIMITIVE ROOTS CHAPTER 9. PRIMITIVE ROOTS

Proof. Let
e = pe11 · · · perr ,
where p1 , . . . , pr are distinct primes.
Suppose i ∈ [1, r]. There must be an element ai whose order is divisible
by pei i ; for otherwise we could take e/pi as exponent in place of e. Let

order(ai ) = pei i qi .

Then
bi = aqi i
has order pei i .
Let
a = b1 · · · br .
Since the orders pe11 , . . . , perr of b1 , . . . , br are mutually coprime it follows from
the last Lemma that that the order of a is

pe11 · · · perr = e.

It follows from the first and last of these 3 Lemmas that we can find an
element a ∈ F × of order q − 1. In other words, F × is cyclic.

9.2 Primitive roots

Definition 9.1. A generator of (Z/p)× is called a primitive root mod p.

Example: Take p = 7. Then

23 ≡ 1 mod 7;

so 2 has order 3 mod 7, and is not a primitive root.

However,
32 ≡ 2 mod 7, 33 ≡ 6 ≡ −1 mod 7.
Since the order of an element divides the order of the group, which is 6 in
this case, it follows that 3 has order 6 mod 7, and so is a primitive root.
If g generates the cyclic group G then so does g −1 . Hence

3−1 ≡ 5 mod 7

is also a primitive root mod 7.

09-2317 9–3
9.2. PRIMITIVE ROOTS CHAPTER 9. PRIMITIVE ROOTS

Proposition 9.1. If a is a primitive root mod p then ar is a primitive root

if and only if gcd(r, p − 1) = 1.
Proof. This is really a result from elementary group theory: If G is a cyclic
group of order n generated by g, then g r is also a generator if and only if
gcd(r, n) = 1.
For suppose gcd(r, n) = 1. If g r has order d then

(g r )d = e,

ie

g rd = e.

But since gcd(r, n) = 1

rd = n =⇒ d = n.
Conversely, suppose g r generates the group. Then g is a power of g r , say

g = (g r )s = g rs .

Hence
rs ≡ 1 mod n,
and in particular gcd(r, n) = 1.
Corollary 9.1. There are φ(p − 1) primitive roots mod p.
Example: Suppose p = 11. Then (Z/11)× has order 10, so its elements
have orders 1,2,5 or 10. Now

25 = 32 ≡ −1 mod 11.

So 2 must be a primitive root mod 11.

There are
φ(10) = 4
primitive roots mod 11, namely

2, 23 , 27 , 29 mod 11,

ie

2, 8, 7, 6.

09-2317 9–4
9.3. PRIME POWER MODULI CHAPTER 9. PRIMITIVE ROOTS

9.3 Prime power moduli

Suppose
n = pe11 . . . perr .
Then
(Z/n)× = (Z/pe11 )× × · · · × (Z/pe11 )× .
Thus the structure of the multiplicative groups (Z/n)× will be completely
determined once we know the structure of (Z/pe )× for each prime power pe .
It turns out that we have already done most of the work in determining the
structure of (Z/p)× .

Proposition 9.2. If p is an odd prime number then the multiplicative group

(Z/pe )×

is cyclic for all e ≥ 1.

Proof. We have proved the result for e = 1. We derive the result for e > 1
in the following way.
The group (Z/pe )× has order

φ(pe ) = pe−1 (p − 1).

By the Theorem, there exists an element a with

order(a mod p) = p − 1.

Evidently
order(a mod p) | order(a mod pe ).
Thus the order of a mod pe is divisible by p − 1, say

order(a mod pe ) = (p − 1)r.

Then
order(ar mod pe ) = p − 1.
It is therefore sufficient by Lemma 9.2 to show that there exists an element
of order pe−1 in the group.
The elements in (Z/pe )× of the form x = 1 + py form a subgroup

S = {x ∈ (Z/pe )× : x ≡ 1 mod p}

of order pe−1 . It suffices to show that this subgroup is cyclic.

09-2317 9–5
9.3. PRIME POWER MODULI CHAPTER 9. PRIMITIVE ROOTS

That is relatively straightforward. Each element of the group has order

p for some j. We have to show that some element x = 1 + py has order pe−1 ,
j

ie
e−2
(1 + py)p 6≡ 1 mod pe .
By the binomial theorem,
 e−2   e−2 
pe−2 e−2 p 2 2 p
(1 + py) =1+p py + py + p3 y 3 + · · · .
2 3

We claim that all the terms after the first two are divisible by pe , ie
 e−2 
e p
p | pr y r
r

for r ≥ 2.
For
 e−2 
p pe−2 (pe−2 − 1) · · · (pe−2 − r + 1)
=
r 1 · 2···r
e−2
p (p − 1) · · · (pe−2 − r + 1)
e−2
= ·
r 1 · 2 · · · (r − 1)
e−2
 e−2 
p p −1
= · .
r r−1

Thus if
pf k r
(ie pf | r but pf +1 - r) then
 e−2 
e−2−f p
p | .
r

Hence
pe−2 r r
 
e−2−f +r
p | py .
r
We must show that

e − 2 − f + r ≥ e,

ie

r ≥ f + 2.

09-2317 9–6
9.3. PRIME POWER MODULI CHAPTER 9. PRIMITIVE ROOTS

Now r ≥ pf (since pf | r), so it is sufficient to show that

pf ≥ f + 2,

which is more or less obvious. (If f = 1 then p ≥ 3 since p is an odd prime,

and each time we increase f we multiply the left by p and add 1 to the right.)
It follows that
e−2
(1 + py)p ≡ 1 + pe−1 y mod pe .

Thus any element of the form 1 + py where y is not divisible by p (for

example, 1 + p) must have multiplicative order pe−1 , and so must generate
S. In particular the subgroup S is cyclic, and so (Z/pe )× is cyclic.
Turning to p = 2, it is evident that (Z/2)× is trivial, while (Z/4)× = C2 .
Proposition 9.3. If e ≥ 3 then

(Z/2e )× ∼
= C2 × C2e−2 .

Proof. Since
φ(2e ) = 2e−1 ,
(Z/2e )× contains 2e−1 elements.
We argue as we did for odd p, except that now we take the elements in
(Z/2e )× of the form x = 1 + 22 y, forming the subgroup

S = {x ∈ (Z/2e )× : x ≡ 1 mod 4}

or order 2e−2 .
By the binomial theorem,
 e−3   e−3 
2 2e−3 e−3 2 2 4 2 2
(1 + 2 y) =1+2 2 y+ 2y + 26 y 3 + · · · .
2 3
As before, all the terms after the first two are divisible by 2e , ie
 e−3 
e p
2 | 22r y r
r
for r ≥ 2. For  e−3 
2e−3
 e−3 
2 2 −1
= · .
r r r−1
Thus if 2f k r it is sufficient to show that

e − 3 − f + 2r ≥ e,

09-2317 9–7
9.3. PRIME POWER MODULI CHAPTER 9. PRIMITIVE ROOTS

ie

2r ≥ f + 3,

which follows easily from the fact that

r ≥ 2f .

Thus any element of the form 1 + 22 y with y odd (for example, 5) must
have multiplicative order 2e−2 . So the subgroup S is cyclic of this order.
Now let
C = {±1 mod 2e }.
This is a subgroup of order 2. Also it is clear that

C ∩ S = {1}.

It follows that
(Z/2e )× = C × S ∼
= C2 × C2e−2 ,
as required.
Example: Consider
(Z/8)× = {1, 3, 5, 7}.
All the elements except 1 have order 2, so

(Z/8)× = C2 × C2 .

Concretely,
(Z/8)× = {±1} × {1, 5}.

As we said, this allows us to determine the structure of any (Z/n)× .

Example: Suppose n = 48. Then

(Z/48)× = (Z/16)× × (Z/3)×

= (C2 × C8 ) × C2
= C2 × C2 × C8 .

09-2317 9–8
9.4. CARMICHAEL NUMBERS, AGAIN
CHAPTER 9. PRIMITIVE ROOTS

9.4 Carmichael numbers, again

We can now complete the proof of our Proposition on Carmichael numbers
in the last Chapter:

Proposition 9.4. The number n is a Carmichael number if and only if it is

square-free, and
n = p1 p2 · · · p r
where r ≥ 2 and
pi − 1 | n − 1
for i = 1, 2, . . . , r.

Proof. Suppose
n = pe11 · · · perr
is a Carmichael number, ie

xn ≡ x mod n

for all x.
Note first that n must be odd; for otherwise

(−1)n ≡ 1 6≡ −1 mod n.

First we show that n is square-free. For suppose

pe k n,

where e > 1. Then (Z/pe )× , and so (Z/n)× , contains an element x of order

p. But p | n. Hence
xn ≡ 1 6≡ x mod n.
Now suppose p | n.
Then (Z/p)× , and so (Z/n)× , contains an element x of order p − 1. This
element must be coprime to n, so

xn ≡ x mod n =⇒ xn−1 ≡ 1 mod n

=⇒ p − 1 | n − 1.

09-2317 9–9