We begin with three preliminary results about greatest common
divisors, which may be intuitive.
Proof: By Theorem 1, there are integers
Proof: Let
Proof: Let
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.
We return to the proof of Theorem 5.2 The sequence
Proof: Let
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.