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
Next, we generalize case 1 and consider the case of being an arbitary power of a prime.
First, we consider the case where is a power of an odd prime. Powers of
will be considered separately.
Now, we start by considering when is the square of an odd prime.
As the page Proof of Some Primitive Roots Facts shown, if is an odd prime, then
have a primitive root. As it also shown, if
have a primitive root and
have a primitive root, then
have a primitive root for all positive integers
.
It follows that all prime powers (of odd primes) have a primitive root.
Next, we consider the case where is a power of
. We conjecture that the only such
with primitive roots are
and
only.
Theorem 1:
The only powers of with primitive roots are
and
.
Proof: Obviously, and
have primitive roots.
is a primitive root of
and
is a primitive root of
.
Now, if , then we claim that
have no primitive roots.
To see that, we claim that for all odd integers and positive integers
greater than or equal to 3, we have
To show that, we use mathematical induction. The case of is merely the fact that
. Suppose
There there exist a integer such that
Thus,
which completes the inductive argument, which thus completes the theorem. .
As the above have shown, all prime powers with primitive roots are
where is an odd prime and
is an positive integer.
This completes case 2.
Case 3
Now, we consider the case where is not a prime power. More specifically, we wish to show that if
have a prime power and is not a prime power, then
is twice a prime power.
Theorem 2:
If is a positive integer that is not a prime power or twice a prime power, then
have no primitive roots.
Proof: Let have prime factorization
Suppose have a primitive root
. Then Euler's Theorem shows that
so therefore
\[r^{\lcm ({p_1}^{t_1} , {p_2}^{t_2 } , \dots , {p_m}^{t_m})} \equiv 1 \pmod {n}\] (Error compiling LaTeX. Unknown error_msg)
Thus,
\[\phi (n) = \text{ord} _{n} r \le \lcm ({p_1}^{t_1} , {p_2}^{t_2 } , \dots , {p_m}^{t_m})\] (Error compiling LaTeX. Unknown error_msg)
It follows that
are all pairwise relatively prime. However, this implies that there is at most one odd prime power. It follows that is either a prime power twice a prime power.
This completes the third (and last) case.
We have now shown that if have a primitive root, then
is
, a prime power, or twice a prime power. The converse can easily be shown also. This, therefore, completes the proof.