Next: Encryption techniques based on
Up: Introduction to Number Theory
Previous: Primitive roots
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.
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 poly
nomial 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
- ....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
Translated from LaTeX by Scott Sutherland
1998-03-15