3.2. The case of odd prime powers and the general case.
We first show that
primitive roots always exist for powers of odd primes. After that we wrap up and give a
list of all values of m ¥ 2 which possess primitive roots.
Proposition 3.8. Let p be an odd prime and l ¥ 2 an integer. Then Zpl is cyclic; i.e.
there exist primitive roots modulo pl .
Proof. We prove the result in three steps. We first produce a candidate, then prove that
it is indeed a primitive root modulo pl .
Step 1. By Corollary 3.5, we assume g is a primitive root modulo p. Then we have
g p1 1 pmod pq. We claim that we can choose g such that g p1 1 pmod p2 q.
In fact, if g satisfies g p1 1 pmod p2 q, we can consider g p, which is still a primitive
root modulo p. However we have
pg pqp1 gp1 pp 1qgp2p pmod p2q
1 pp 1qgp2p pmod p2q
1 pmod p2q,
which shows that we can replace g by g p and achieve our claim.
Step 2. By Step 1 we can write g p1 1 ap pmod p2 q for some a P Z not divisible by
p. We claim that for each l ¥ 2, we similarly have
q
g φpp 1 a pl1 pmod pl q.
l 1
(3.1)
We prove it by induction on l. When l 2, the claim follows from Step 1. Assume the
claim is true for some l ¥ 2, then we can write
q
g φpp 1 b p l 1
l 1
for some b P Z with a b pmod pq. Then
p¸1
g p q p1 bp
p i ipl1q
φ pl l 1 p
q 1 bp l
b p bp pppl1q .
i 2
i
We know p
i
is divisible p. (Indeed, we have p! i!pp iq! pi by the definition of binomial
coefficients. The left-hand side is divisible by p, hence so is the right-hand side. But p
does not divide i!pp iq! since it is a product of integers less than, and thus coprime to p.
Hence p divides pi .) Therefore for each i ¥ 2, the corresponding term in the summation
is divisible by p1 ipl1q , where 1 ipl 1q ¥ 1 2pl 1q ¥ l 1. The term after the
summation is divisible by pppl1q , where ppl 1q ¥ 3pl 1q ¥ l 1 since p is an odd prime.
Also notice that the difference of a and b is a multiple of p. All this together implies
g φpp q 1 a pl pmod pl 1q.
l
(3.2)
33
Therefore the claim is true for l 1.
Step 3. We show that for each l ¥ 2, the order of g modulo pl is φppl q; i.e. g is a primitive
root modulo pl .
Denote the order of g modulo pl by d. First of all, g d 1 pmod pl q implies g d 1
pmod pq. Since we chose g to be a primitive root modulo p in Step 1, we know that φppq
divides d. Then by (3.2) we have g
l 1
φppl q
1 pmod pl q, hence d divides φppl q. Finally by
(3.1) we have g φpp q 1 pmod pl q, hence d does not divide φppl1 q. These requirements
leave d φppl q as the only possibility.
Remark 3.9. Notice that Steps 2 and 3 in the proof actually shows that: if g is a primitive
root modulo p and g p1 1 pmod p2 q, then g is a primitive root modulo pl for any positive
integer l. This sufficient condition will be handy in looking for primitive roots modulo
higher powers of odd primes; see Exercise 3.1 for an example. In fact, this condition is
also necessary; see Exercise 3.4.
Finally we put all our existing results together and get:
Theorem 3.10. An integer m ¥ 2 possesses primitive roots iff m is of the form 2, 4, pk
or 2pk , where p is an odd prime and k is a positive integer.
Proof. This proof is not covered in lecture and is non-examinable.
We first show that m possesses primitive roots if it has one of the given forms. We already
know this for 2, 4 and pk . In the last case, by Remark 2.20 we have
Z2pk Z2 Zp Zp ,
k k
it follows that Z2pk is cyclic; i.e. 2pk possesses primitive roots.
We then show that n does not possess primitive roots in all other cases. We already know
this for m 2l with l ¥ 3, so we can now assume m is not a power of 2.
We claim that m can be written as a product m1 m2 , where m1 and m2 are coprime,
m1 ¡ 2 and m2 ¡ 2. Indeed, assume m 2a pa11 pa22 pal l is the prime factorisation of m,
where p1 , p2 , , pl are distinct odd primes, a ¥ 0 and ai ¥ 1 for each i. If l ¥ 2, then we
can take m1 pa11 and m2 2a pa22 pal l . Otherwise l 1, hence by assumption a ¥ 2,
then we can take m1 2a and m2 pa11 .
We then have that φpm1 q and φpm2 q are both even by Exercise 1.2 and that Zm
Zm1 Zm2 by Remark 2.20. Since every group of even order has an element of order 2,
both factors have elements of order 2, which implies that Zm has at least two elements
of order 2. Therefore it is not cyclic since a cyclic group contains at most one element of
order 2. Thus m does not possess primitive roots.
34
