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

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

**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

We return to the proof of Theorem 5.^{2} The sequence

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