Next: Encryption techniques based on Up: Introduction to Number Theory Previous: Primitive roots   Contents

## Proof of Theorem 5

This proof unfortunately requires many lemmas. It is probably a good idea to skip over the lemmas as much as possible on a first reading.

We begin with three preliminary results about greatest common divisors, which may be intuitive.

Lemma 11   If and , then .

Proof: By Theorem 1, there are integers with . Together these imply

which is impossible if . height 8pt width 4pt

Lemma 12   If divides and , then .

Proof: Let and . Then

Lemma 13   If , is divisible by , and is divisible by , then is divisible by .

Proof: Let , , and . Then

The key step of the proof begins with any . Let be the smallest positive number for which (there must be such a since implies ). By Lemma 10, if , is a primitive root. If , we will find with for all . If is not a primitive root, we repeat the process, this time with . Since the exponent increases each time, we eventually obtain a primitive root.

Lemma 14   There are at most solutions to a congruence involving a polynomial of degree :

In particular, there are at most with .

Proof: This can be proved in the same way as the corresponding theorem in ordinary algebra: if is a solution, the polynomial can be written as times a polynomial of degree , which by induction has solutions. height 8pt width 4pt

consists of different solutions of . If , let be any non-member of the sequence, with the smallest positive number with . If , we may take , so we will assume from now on. By Lemma 14, , which implies does not divide and . We will use and to construct a number such that for all . The construction is based on two lemmas:

Lemma 15   Suppose that and that are the smallest positive numbers for which . If and , then is divisible by .

Proof: Since , Lemma 9 implies is divisible by . Similarly is divisible by , and Lemma 13 gives the desired result. height 8pt width 4pt

Lemma 16   Let , , . There are such that (i)  and (ii) .

Proof: Let be the largest divisor of for which , . The maximality of implies . By Lemma 11, .

The maximality of and Lemma 12 implies . Since implies , Lemma 11 implies . Thus the maximality of implies . Lemma 11 now implies .

Applying Lemma 11 to the conclusions of the preceding paragraphs yields . height 8pt width 4pt

We can finally complete the proof of Theorem 5. With the notation of Lemma 16, let . For , for . A similar assertion holds for . The other conditions of Lemma 15 are satisfied, and we can conclude that if and only if is a multiple of . height 8pt width 4pt

This proof does not give us an efficient procedure for finding a primitive root for large primes , but the reason may not be obvious. The steps implicit in the lemmas can all be carried out efficiently. The one problem is the choice of , which was required to be a non-member of the set of powers of . It is too inefficient to list all the powers of if is large, and no significantly better way of finding a non-member is known.

#### Footnotes

...proot.2
This proof uses ideas of Michael Fischer, who pointed out an error in an earlier version.

Next: Encryption techniques based on Up: Introduction to Number Theory Previous: Primitive roots   Contents
Translated from LaTeX by Scott Sutherland
2002-12-14