Chap5 PDF

Download as pdf or txt
Download as pdf or txt
You are on page 1of 9

Chapter 5

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.

5.1 Orders and Primitive Roots


With gcd(a, n) = 1, we know that the sequence a % n, a2 % n, a3 % n, . . .
must eventually reach 1 and make a loop back to the first term. In fact,
Euler’s theorem says that the length of this periodicity is at most φ(n). We
will define this length, for a given a, and ask whether it can sometimes equal
φ(n).
Definition. Suppose a and n > 0 are relatively prime. The order of a modulo
n is the smallest positive integer k such that ak % n = 1. We denote this
quantity by |a|n , or simply |a| when there is no ambiguity. For example,
|2|7 = 3 because x = 3 is the smallest positive solution to the congruence
2x ≡ 1 (mod 7).
Exercise 5.1. Find these orders.
a) |3|7
b) |3|10
c) |5|12
d) |7|24
e) |4|25
Exercise 5.2. Suppose |a| = 6. Find |ak | for k = 2, 3, 4, 5, 6.

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.

a|b| |ab| = a|b| |ab| (b|b| )|ab| = (ab)|ab| |b| ≡ 1 (mod n)

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

Primitive roots, described earlier, turn out to be exactly the integers


whose orders equal φ(n). This distinguishing feature is now adopted as the
formal definition of a primitive root, and we shall then demonstrate that the
two descriptions are equivalent.
Definition. An integer g is called a primitive root modulo n if |g|n = φ(n).
For example, 3 is a primitive root modulo 7 because |3|7 = 6 = φ(7).
Exercise 5.6. Is 13 a primitive root modulo 257?
As with order, the concept of primitive roots also extends to residue
classes. Thus, g is a primitive root modulo n if and only if every integer in
[g]n is too. Accordingly, we use the word distinct or incongruent primitive
roots modulo n when we mean that they belong to different residue classes.
So, to search for a primitive root modulo n it suffices to look at a reduced
residue system modulo n. For example, a reduced residue system modulo 8
is {1, 3, 5, 7}. None of these elements has order equals 4, where φ(8) = 4.
(See Exercise 3.1.) We conclude that primitive roots modulo 8 do not exist.
Exercise 5.7. Find all the primitive roots modulo n, if any.
a) n = 6
b) n = 7
c) n = 9
d) n = 10
e) n = 12
Proposition 5.2. The following statements are equivalent.
1) g is a primitive root modulo n.
2) G = {g, g 2 , g 3 , . . . , g φ(n) } is a reduced residue system modulo n.
3) g x ≡ c (mod n) has a solution whenever gcd(c, n) = 1.
4) g k is a primitive root modulo n whenever gcd(k, φ(n)) = 1.
Proof. Note that statements (1) and (4) are equivalent, as a special case of
Proposition 5.1(3). We will complete the proof going (1) → (2) → (3) → (1).
It is clear that the exponents 1, 2, . . . , φ(n) in G are all distinct modulo
φ(n). So if |g|n = φ(n) then, by Proposition 5.1(2), g, g 2 , . . . , g φ(n) are all
distinct modulo n, and G is a reduced residue system. As a consequence,
the congruence g x ≡ c (mod n) finds a unique solution in 1 ≤ x ≤ φ(n),
provided that gcd(c, n) = 1. More generally, if (3) holds then we can find
a reduced residue system modulo n in the form G′ = {g k1 , g k2 , . . . , g kφ(n) }.
By Proposition 5.1(2), these exponents k1 , k2 , . . . , kφ(n) may be reduced
mod |g|n . But, as |g|n ≤ φ(n), the elements of G′ would not be all distinct,
unless |g|n = φ(n). ▽
46 Theory of Numbers

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.

5.2 The Existence of Primitive Roots


We have seen that primitive roots exist with some moduli, but not all of
them. The main objective in this section is to prove that primitive roots
exist for any prime modulus. For the general composite case, we will state
the theorem but delay its proof to a later time.
Definition. Let f (x) = a0 + a1 x + a2 x2 + · · · + ar xr be a polynomial with
integer coefficients. We define the degree of f (x) modulo n to be the largest
exponent k for which n ∤ ak . If no such k exists then we say that f (x) is the
zero polynomial modulo n, since then f (c) ≡ 0 (mod n) for any integer c.
For example, the polynomial 14x5 − 6x2 + 35 has degree 5 modulo 3,
degree 0 modulo 2, and degree 2 modulo 7. For convenience, we will use the
term zero of f (x) modulo n, by which we mean a solution to the congruence
f (x) ≡ 0 (mod n).
Theorem 5.3. Every polynomial f (x) = a0 + a1 x + a2 x2 + · · · + ak xk of
degree k, modulo a prime p, has at most k incongruent zeros.
Proof. The case k = 0 means that f (c) ≡ a0 (mod p) for all integers c, where
p ∤ a0 . Accordingly, there cannot be a solution to f (x) ≡ 0 (mod p).
By way of induction, assume that the theorem is true up to degree k − 1,
modulo p. Let f (x) = a0 + a1 x + · · · + ak xk with p ∤ ak . If f (x) has less than
k zeros, then there is nothing to prove. Else, let r1 , r2 , . . . , rk be distinct
zeros of f (x) modulo p, and let
g(x) = f (x) − ak (x − r1 )(x − r2 ) · · · (x − rk )
Note that the degree of g(x) modulo p is now less than k, and yet g(x)
claims all these k zeros of f (x) as its own. By our induction hypothesis, this
is impossible unless g(x) is the zero polynomial modulo p. Thus,
f (x) ≡ ak (x − r1 )(x − r2 ) · · · (x − rk ) (mod p)
ISBN – 1419687352 47

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

must have orders q j modulo p, where j ≤ e, according to Proposition 5.1(1).


At least one of these zeros must have order q e , because those with j < e
e−1
constitute the zeros of xq − 1 modulo p—only q e−1 of them. (In fact,
e e−1 e
there will be q − q = φ(q ) zeros of order Q q e .) By Proposition 5.1(4), the
ei
product of integers of orders qi is of order qiei = p − 1, i.e., a primitive
root modulo p. ▽
Exercise 5.11. Count how many primitive roots modulo these primes.
a) p = 11
b) p = 37
c) p = 89
d) p = 101
Exercise 5.12. Show that there are exactly φ(d) incongruent integers of
order d modulo p, whenever d | (p − 1).
The existence of primitive roots modulo a composite is dealt with by the
following theorem, whose proof is set aside in Appendix C, as none of the
subsequent results will be dependent upon it.
48 Theory of Numbers

Theorem 5.6 (Primitive Root Theorem). A primitive root modulo n exists


if and only if n = 1, 2, 4, pk , or 2pk , for any prime p > 2 and k > 0.
Exercise 5.13. Is there a primitive root modulo n? How many?
a) n = 25
b) n = 50
c) n = 100
d) n = 1250
e) n = 19392
Exercise 5.14. When we have primitive roots, prove that
Y
a ≡ −1 (mod n)
a∈G

where G is any reduced residue system modulo n. In particular, if n is a


prime number, use this fact to prove again Wilson’s theorem.
Concluding this section, the next result is actually the first step toward
proving Theorem 5.6, but it is included here considering its usefulness in
later chapters.
Proposition 5.7. Let g be a primitive root modulo a prime p. Then either
g or g + p is a primitive root modulo p2 .
Proof. Being in the same residue class, g+p is another primitive root modulo
p. Now if g p−1 ≡ 1 (mod p2 ) then, by the binomial theorem, (Theorem B.3)

(g + p)p−1 ≡ g p−1 + (p − 1)pg p−2 ≡ 1 − pg p−2 6≡ 1 (mod p2 )

Let a = g or g + p, whichever gives ap−1 6≡ 1 (mod p2 ). Now the congruence


a|a|p2 ≡ 1 (mod p) implies that |a|p2 is a multiple of p − 1. At the same time,
|a|p2 | φ(p2 ) = p(p − 1). The only way both claims can be true is when
|a|p2 = p(p − 1), and a is a primitive root modulo p2 . ▽
Exercise 5.15. Give an example of a primitive root modulo p which is not
a primitive root modulo p2 .
Knowing exactly when a primitive root exists does not really help us
in finding one. It remains open, for instance, to determine modulo which
primes 2 is a primitive root.1
Exercise 5.16. Find three primes modulo which 2 is not a primitive root.
1 There is a famous Artin’s conjecture, which predicts that the number 2 is a primitive

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

5.3 Finding Discrete Logarithms


Suppose that, instead of computing b = ak % n, we are given b and asked
to find the exponent k. In ordinary arithmetic, we would be computing the
logarithm of b to the base a, that is, k = loga b. In modular arithmetic,
however, this discrete logarithm problem is very difficult to solve, especially
so when n is large.
For a relatively small modulus n, and with a known primitive root g,
finding a discrete logarithm commonly involves a preconstructed table2 of
discrete logarithms base g, via a technique illustrated in the next example.
Example. Let us solve the congruence 5x ≡ −1 (mod 13). We choose g = 2,
a primitive root modulo 13, and construct a reduced residue system modulo
13 represented by powers of 2. In general, this is made possible by Proposi-

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).

This technique of replacing the integer by its exponent, or index, with


respect to a chosen primitive root, is named index arithmetic. With this
method, we will be able to tackle some more root extraction problems. The
next result along this line is somewhat a generalization of Theorem 4.9.
2 In an analogous way, an extensive table of ordinary logarithms base 10 was made

available in the old days before pocket calculators were invented.


50 Theory of Numbers

Theorem 5.8. Suppose gcd(a, n) = 1, and assume there exists a primitive


root modulo n. Let d = gcd(k, φ(n)). Then the congruence xk ≡ a (mod n)
has a solution if and only if aφ(n)/d ≡ 1 (mod n), in which case there are
exactly d distinct solutions modulo n.
Proof. Let g be a primitive root modulo n, and let g c ≡ a (mod n) for
some c ≥ 0. It suffices to seek a solution x in the reduced residue system
G = {g, g 2 , . . . , g φ(n) }. By the substitution x = g y , the three congruences
xk ≡ a (mod n)
g ky ≡ g c (mod n)
ky ≡ c (mod φ(n))
can be shown equivalent one to another, and they have a solution if and
only if d | c. In that case, by Theorem 3.5, the solution set is given by a
unique y-value modulo φ(n)/d, i.e., exactly d solutions for x in G.
To complete the proof, we will show that the condition d | c is necessary
and sufficient to have aφ(n)/d ≡ g φ(n)c/d ≡ 1 (mod n). This last congruence,
by Proposition 5.1(1), holds if and only if |g|n | φ(n)c/d—that is, if and only
if c/d is an integer, since |g|n = φ(n). ▽
Example. Consider the congruence x2 ≡ 3 (mod 13). We have gcd(2, 12) = 2,
and we check that 312/2 = 36 ≡ 1 (mod 13), so we know a solution exists.
Using Table 5.1, we obtain 22y ≡ 24 (mod 13), and hence 2y ≡ 4 (mod 12).
The solution set for y is [2]6 , which gives two distinct solutions x = 22 and
x = 28 , corresponding to two residue classes [4]13 and [9]13 , respectively.
Exercise 5.20. Solve each congruence, when possible.
a) x2 ≡ 10 (mod 13)
b) x9 ≡ 1 (mod 13)
c) x5 ≡ 3 (mod 14)
d) x4 ≡ 5 (mod 17)
e) x8 ≡ 16 (mod 17)
Exercise 5.21. Without solving it, count how many distinct solutions the
congruence x45 ≡ 53 (mod 729) has, if any at all.
Corollary 5.9. Let p be a prime not dividing a, and let d = gcd(k, p − 1).
The congruence xk ≡ a (mod p) has a solution if and only if a(p−1)/d ≡
1 (mod p), in which case it has exactly d incongruent solutions modulo p.
Proof. Primitive roots exist modulo any prime, so Theorem 5.8 applies. ▽
Exercise 5.22. For any odd prime p, prove that x2 ≡ −1 (mod p) has a
solution if and only if p % 4 = 1. Similarly, show that x4 ≡ −1 (mod p) has
a solution if and only if p % 8 = 1.
ISBN – 1419687352 51

5.4 Secret Key Exchange [Project 5]


For cryptological purposes, Alia and Bob need to establish a common secret
key. However, the only available means of communication between them is
the mobile phone, which they know is being tapped by the enemy. They
resort to the Diffie-Hellman key exchange protocol [DH76] as follows.
Alia picks a large prime p, a primitive root g, and another number m < p.
She gives to Bob, over the nonsecure line, the numbers p, g, and a = g m % p,
but keeps m secret. In the next step, Bob selects a secret number n < p
and gives to Alia b = g n % p. They agree that their common secret key is
g mn % p, which Alia obtains by computing bm % p and Bob, independently,
by an % p. Both of them know the successive squaring algorithm.
If Cobra, the enemy, gathers this information—but not m and n for
they are not transmitted across—then in order to capture the secret key,
he will have to solve the congruence g x ≡ a (mod p) from Alia’s number, or
alternately g x ≡ b (mod p) from Bob’s. But there is no efficient algorithm
known for solving the discrete logarithm problem and, for large p, it is just
not computationally feasible to do it by trial and error.
Project 5.4.1. For a small example, Alia sends to Bob the numbers p =
8191, g = 3, and 3m % 8191 = 8119. Bob, in his turn, sends to Alia
3n % 8191 = 3731.
a) Try your luck in finding m or n.
b) Could there be a way to find the secret key without knowing m or n?
c) Is it really necessary for g to be a primitive root modulo p?
d) What could go wrong if Cobra is aware of this protocol and he, with evil
intent, is mediating the communication between Alia and Bob?
Project 5.4.2. The difficulty in solving the discrete logarithm problem can
in fact be used to develop an algorithm for another public-key cryptosystem,
by the name of ElGamal encryption. Write a paper on this subject.

You might also like