Proof of the Existence of Primitive Roots
This page is dedicated to proving the existence of primitive roots for certain integers.
Contents
[hide]Statement
Let be a positive integer. Then
have a primitive root if and only if
Proof
We start case by case, starting with the most basic case:
Case 1
In this case, we have , where
is prime.
We wish to show that have a primitive root.
To do so, we first need a few lemmas regarding the solutions of polynomial congruences.
Lemma 1 (Lagrange's Theorem):
Let be a prime and let
be a polynomial with degree (where
is an integer), with integer coeficients and leading coeficient
not divisible by
.
Then have at most
incongruent roots modulo
.
Note that this is a number theory analogue of the fundamental theorem of algebra.
Note also that this theorem only holds for primes. For example, when , there is
incongruent roots (as the reader should verify) modulo
, but this does not contradicts Lagrange's theorem since
is composite.
Proof: We proceed by mathematical induction. When , the statement is obvious; it merely states that a linear congruence have at most one solution modulo
, which is true since
.
Now, suppose the theorem holds for a (n-1)th degree polynomial. Let be a nth degree polynomial with leading coeficient relatively prime to
. Then assume it have
incongruent roots modulo
, say
. Then,
for a (n-1)th degree polynomial with leading coeficient
. Then
satisfy the conditions of the inductive hypothesis.
Now, let be an arbitary integer with
.
. Thus,
since
Thus are all roots of
. This contradicts the inductive hypothesis, and thus establishes the lemma.
.
Now, we have a useful corollary:
Corollary (Lemma 2):
Let be prime and let
be a divisor of
. Then the polynomial
have exactly
incongruent roots modulo
.
Proof: Let . We have
for a degree polynomial
. By Fermat's Little Theorem,
have exactly
roots modulo
. By Lagrange's Theorem,
have at most
incongruent roots modulo
. Thus,
have at least
roots modulo
. On the other hand, Lagrange's Theorem again implies
have at most
incongruent roots. Thus,
have exactly
roots.
This result can be used to prove a result regarding the number of integer of a certain integer a prime can have. Before we state and prove that, we present yet another lemma.
Lemma 3:
Let be prime and let
be a divisor of
. Then the number of positive integers less than
of order
modulo
do not exceed
.
Proof: Let denote the number of positive integers less than
of order
modulo
.
Now, if , the result is trivial. Assume
, and that
is an integer with order
modulo
. Then the integers
are incongruent modulo . Also, each of those integers are a root of
. By Lemma 3, those are the only roots. Thus, every possible integer with order
modulo
must be a power of
. Obviously, the exponent of
must be relatively prime to
, or otherwise there exist a smaller solution to
(for
) than
, which would cause
to be less than
. Therefore, the result follow by the definition of the Euler-Phi Function.
.
In fact, the number of positive integers less than of order
modulo
is exactly
, as the following lemma shows:
Lemma 4:
Let be prime and let
be a divisor of
. Then the number of positive integers less than
of order
modulo
is exactly
.
Proof: As the page Proof of Some Primitive Roots Facts proved, the order of an integer modulo divides
, we have
By some Euler-Phi Function facts, we know that
Lemma 3 implies for each
, so it follows that
for every
.
.
An easy corollary of that is when we take , and we get that every prime have
primitive roots. We have thus shown that every prime have a primitive roots.
Case 1 is completed.
Case 2
UNDER CONSTRUCTION