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