Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Proof of the Existence of Primitive Roots

Revision as of 21:36, 19 January 2025 by Ddk001 (talk | contribs) (no that is NOT the easiest case)

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Proof_of_the_Existence_of_Primitive_Roots&oldid=240661"