Difference between revisions of "Proof of the Existence of Primitive Roots"

Revision as of 21:36, 19 January 2025

This page is dedicated to proving the existence of primitive roots for certain integers.

Statement

Let $n$ be a positive integer. Then $n$ have a primitive root if and only if

$n=2,4,p^t, \text{or} , 2p^t$

Proof

We start case by case, starting with the most basic case:

Case 1

In this case, we have $n=p$ , where $p$ is prime.

We wish to show that $n$ 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 $p$ be a prime and let

$f(x)= \sum _{i=0}^{n} (a_i \cdot x^i)$

be a polynomial with degree $n$ (where $n$ is an integer), with integer coeficients and leading coeficient $a_n$ not divisible by $p$ .

Then $f(x)$ have at most $n$ incongruent roots modulo $p$ .

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 $f(x)=x^2-x$ , there is $4$ incongruent roots (as the reader should verify) modulo $6$ , but this does not contradicts Lagrange's theorem since $6$ is composite.

Proof: We proceed by mathematical induction. When $n=1$ , the statement is obvious; it merely states that a linear congruence have at most one solution modulo $p$ , which is true since $\gcd (a_1,p)=1$ .

Now, suppose the theorem holds for a (n-1)th degree polynomial. Let $f(x)$ be a nth degree polynomial with leading coeficient relatively prime to $p$ . Then assume it have $n+1$ incongruent roots modulo $p$ , say $c_1, c_2, \dots , c_{n+1}$ . Then,

$f(x) - f(c_1) = \sum _{i=0}^{n} a_i \cdot (x^i- {c_1}^i)$

$=\sum _{i=0}^{n} a_i \cdot (x-c_1) \cdot (\sum _{j=0}^{i-1} x^j \cdot {c_1}^{i-1-j})$

$=(x-c_1) \cdot g(x)$

for a (n-1)th degree polynomial $g(x)$ with leading coeficient $a_{n}$ . Then $g(x)$ satisfy the conditions of the inductive hypothesis.

Now, let $k$ be an arbitary integer with $1 \le k \le n+1$ . $f(c_k) \equiv 0 \equiv f(c_i) \pmod {p}$ . Thus,

$0 \equiv f(c_k) - f(c_1) = (c_k-c_1) g(c_k) \pmod {p}$

$\implies g(c_k) \equiv 0 \pmod {p}$

since

$c_k \not\equiv c_1 \pmod {p}$

Thus $c_2 , c_2 , \dots , c_{n+1}$ are all roots of $g(x)$ . This contradicts the inductive hypothesis, and thus establishes the lemma. $\square$ .

Now, we have a useful corollary:

Corollary (Lemma 2):

Let $p$ be prime and let $d$ be a divisor of $p-1$ . Then the polynomial $x^d -1$ have exactly $d$ incongruent roots modulo $p$ .

Proof: Let $p-1 =d \cdot e$ . We have

$x^{p-1} -1= (x^d-1) g(x)$

for a $p-1-d$ degree polynomial $g(x)$ . By Fermat's Little Theorem, $x^{p-1}-1$ have exactly $p-1$ roots modulo $p$ . By Lagrange's Theorem, $g(x)$ have at most $p-d-1$ incongruent roots modulo $p$ . Thus, $x^d -1$ have at least $d$ roots modulo $p$ . On the other hand, Lagrange's Theorem again implies $x^d -1$ have at most $d$ incongruent roots. Thus, $x^d -1$ have exactly $d$ roots. $\square$

This result can be used to prove a result regarding the number of integer of a certain integer a prime $p$ can have. Before we state and prove that, we present yet another lemma.

Lemma 3:

Let $p$ be prime and let $d$ be a divisor of $p-1$ . Then the number of positive integers less than $p$ of order $d$ modulo $p$ do not exceed $\phi (d)$ .

Proof: Let $F(d)$ denote the number of positive integers less than $p$ of order $d$ modulo $p$ .

Now, if $F(d)=0$ , the result is trivial. Assume $F(d) \ne 0$ , and that $a$ is an integer with order $d$ modulo $p$ . Then the integers

$a, a^2, \dots , a^d$

are incongruent modulo $p$ . Also, each of those integers are a root of $x^d-1$ . By Lemma 3, those are the only roots. Thus, every possible integer with order $d$ modulo $p$ must be a power of $a$ . Obviously, the exponent of $a$ must be relatively prime to $d$ , or otherwise there exist a smaller solution to $(a^k)^x \equiv 1 \pmod {p}$ (for $x$ ) than $d$ , which would cause $\text {ord} _d a^k$ to be less than $d$ . Therefore, the result follow by the definition of the Euler-Phi Function. $\square$ .

In fact, the number of positive integers less than $p$ of order $d$ modulo $p$ is exactly $\phi (d)$ , as the following lemma shows:

Lemma 4:

Let $p$ be prime and let $d$ be a divisor of $p-1$ . Then the number of positive integers less than $p$ of order $d$ modulo $p$ is exactly $\phi (d)$ .

Proof: As the page Proof of Some Primitive Roots Facts proved, the order of an integer modulo $p$ divides $p-1$ , we have

$\sum _{d|p-1} F(d) = p-1$

By some Euler-Phi Function facts, we know that

$\sum _{d|p-1} \phi (d) = p-1$

Lemma 3 implies $F(d) \le \phi (d)$ for each $d|p-1$ , so it follows that $F(d)= \phi (d)$ for every $d$ . $\square$ .

An easy corollary of that is when we take $d=p-1$ , and we get that every prime have $\phi (p-1)$ primitive roots. We have thus shown that every prime have a primitive roots.

Case 1 is completed.

Case 2

UNDER CONSTRUCTION

@@ Line 8: / Line 8: @@
 ==Proof==
-We start case by case, starting with the easiest case:
+We start case by case, starting with the most basic case:
 ===Case 1===

Page

Toolbox

Search