Chap5 PDF
Chap5 PDF
Chap5 PDF
Primitive Roots
The name primitive root applies to a number a whose powers can be used
to represent a reduced residue system modulo n. Primitive roots are there-
fore generators in that sense, and their properties will be very instrumental
in subsequent developments of the theory of congruences, especially where
exponentiation is involved.
43
44 Theory of Numbers
From now on we agree that the notation |a|n implicitly assumes the
condition gcd(a, n) = 1, for otherwise it makes no sense. In particular, by
Euler’s theorem, |a|n ≤ φ(n). It is also clear that the definition of order
extends to residue classes, for we have |a|n = |b|n whenever a ≡ b (mod n).
Exercise 5.3. Investigate true or false.
a) |− a| = |a|
b) |a−1 | = |a|
c) If |a|n = |b|n then a ≡ b (mod n).
d) If aj ≡ ak (mod n) then j ≡ k (mod n).
e) If gcd(a, n) > 1, then ax ≡ 1 (mod n) has no solution.
Exercise 5.4. Prove that if |a|n = n − 1 then n is a prime.
Proposition 5.1. Fix a modulus n > 0. Then
1) ak ≡ 1 (mod n) if and only if |a|n | k. In particular, |a|n | φ(n).
2) aj ≡ ak (mod n) if and only if j ≡ k (mod |a|n ).
3) |a| = |ak | gcd(k, |a|) for any k ≥ 1. In particular, |ak | = |a| if and only if
gcd(k, |a|) = 1.
4) |ab| = |a| |b| if gcd(|a|, |b|) = 1.
Proof. 1) Let j = ⌊k/|a|n ⌋ so that we may write k = j|a|n + k % |a|n . Then
ak = (a|a|n )j · ak % |a|n ≡ ak % |a|n (mod n). But k % |a|n < |a|n , hence the
congruence ak ≡ 1 (mod n) can hold if and only if k % |a|n = 0.
2) The congruence aj ≡ ak (mod n) is equivalent to aj−k ≡ 1 (mod n), and
the result follows from (1).
3) The positive integer |ak | is the least x for which akx ≡ 1 (mod n). This
congruence is equivalent to kx ≡ 0 (mod |a|) and to x ≡ 0 (mod |a|/d),
where d = gcd(k, |a|)—according to (1) and Theorem 3.5, respectively.
Hence, |ak | = |a|/d as claimed.
4) Suppose gcd(|a|, |b|) = 1. The following congruence holds.
Then by (1) we have |a| | |b| |ab| and in turn, by Euclid’s lemma, |a| | |ab|.
Now by symmetry |b| | |ab|, hence |a| |b| | |ab| by Proposition 1.8(2). It
is clear, however, that |ab| ≤ |a| |b|, so it follows that |ab| = |a| |b|. ▽
n
Exercise 5.5. Show that |2|Fn = 2n+1 for the Fermat number Fn = 22 +1.
ISBN – 1419687352 45
Exercise 5.8. If any exists, show that there are exactly φ(φ(n)) primitive
roots modulo n.
Exercise 5.9. Find all the primitive roots modulo 37 among the numbers
2, 22 , 23 , . . . , 236 , given that no two are congruent.
Exercise 5.10. Prove the following claims, where p denotes any odd prime.
a) If g is a primitive root modulo p then g (p−1)/2 ≡ −1 (mod p).
b) The number 4 is not a primitive root modulo p.
c) The product of two primitive roots modulo p is not a primitive root.
d) If p % 4 = 1, then g is a primitive root modulo p if and only if −g is too.
and by Theorem 2.3, f (x) ≡ 0 (mod p) if and only if x ≡ ri (mod p). This
shows that f (x) can have no more zeros other than these k. ▽
Corollary 5.4. If p is a prime number and d | (p − 1), then the congruence
xd ≡ 1 (mod p) has exactly d solutions modulo p.
Proof. Let p − 1 = dk and f (x) = (xd )k−1 + (xd )k−2 + · · · + xd + 1. We have
the following polynomial identity.
xp−1 − 1 = (xd − 1)f (x)
By Fermat’s little theorem, xp−1 − 1 has exactly p − 1 = dk zeros modulo
p, each of which must also be a zero of either xd − 1 or f (x), as p is prime.
But, by Theorem 5.3, the latter two polynomials have no more than d and
dk − d zeros, respectively. The only way this can happen is when xd − 1 has
exactly d zeros, and f (x) exactly dk − d, modulo p. ▽
At this point we are ready to present our goal of showing the existence
of primitive roots modulo any prime. We even know their exact number.
Theorem 5.5. There are exactly φ(p − 1) incongruent primitive roots mod-
ulo every prime p.
Proof. In view of Proposition 5.2(4), (see also Exercise 5.8) it suffices to
show that at least one primitiveQroot exists. Let p − 1 be factored into
prime powers, written p − 1 = qiei , with ei ≥ 1. By Corollary 5.4, for
ei e
each q = qi , there are exactly q zeros of xq − 1 modulo p, all of which
e e
root modulo infinitely many primes, about one in every three. Up to 10,000, you can
check this claim against the table of primes given in the unnumbered appendices.
ISBN – 1419687352 49
k 1 2 3 4 5 6 7 8 9 10 11 12
2k % 13 2 4 8 3 6 12 11 9 5 10 7 1
Table 5.1: Powers of 2, a primitive root, modulo 13.
tion 5.2(2). Next, we rewrite the congruence using only powers of 2. Here,
(29 )x ≡ 26 (mod 13). This is equivalent, by Proposition 5.1(2), to the con-
gruence 9x ≡ 6 (mod 12). The linear congruence theorem takes it from here.
We have gcd(9, 12) = 3 and a particular solution x0 = 2, hence the general
solution given by the class [2]4 .
Exercise 5.17. Solve the discrete logarithm problems, all modulo 13.
a) 6x ≡ 9 (mod 13)
b) 9x ≡ 6 (mod 13)
c) 10x ≡ 3 (mod 13)
d) 11x ≡ 7x (mod 13)
Exercise 5.18. Use Table 5.1 to find all the solutions to 2x ≡ x (mod 13).
Exercise 5.19. Find a primitive root modulo 23 and use it, in a similar
manner, to help solve the congruence 3x ≡ 2 (mod 23).