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

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

(Created page with "This page is dedicated to proving the existence of primitive roots for certain integers. ==Statement== Let <math>n</math> be a positive integer. Then <math>n</math> have a p...")
 
(→‎Proof)
Line 7: Line 7:
  
 
==Proof==
 
==Proof==
 +
 +
We start case by case, starting with the easiest case:
 +
 +
===Case 1===
 +
In this case, we have <math>n=p</math>, where <math>p</math> is prime.
 +
 +
We wish to show that <math>n</math> 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 <math>p</math> be a prime and let
 +
 +
<cmath>f(x)= \sum _{i=0}^{n} (a_i \cdot x^i)</cmath>
 +
 +
be a polynomial with degree <math>n</math> (where <math>n</math> is an integer), with integer coeficients and leading coeficient <math>a_n</math> not divisible by <math>p</math>.
 +
 +
Then <math>f(x)</math> have at most <math>n</math> incongruent roots modulo <math>p</math>.
 +
 +
 +
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 <math>f(x)=x^2-x</math>, there is <math>4</math> incongruent roots (as the reader should verify) modulo <math>6</math>, but this does not contradicts Lagrange's theorem since <math>6</math> is composite.
 +
 +
 +
''Proof:'' We proceed by mathematical induction. When <math>n=1</math>, the statement is obvious; it merely states that a linear congruence have at most one solution modulo <math>p</math>, which is true since <math>\gcd (a_1,p)=1</math>.
 +
 +
Now, suppose the theorem holds for a (n-1)th degree polynomial. Let <math>f(x)</math> be a nth degree polynomial with leading coeficient relatively prime to <math>p</math>. Then assume it have <math>n+1</math> incongruent roots modulo <math>p</math>, say <math>c_1, c_2, \dots , c_{n+1}</math>. Then,
 +
 +
<cmath>f(x) - f(c_1) = \sum _{i=0}^{n} a_i \cdot (x^i- {c_1}^i)</cmath>
 +
 +
<cmath>=\sum _{i=0}^{n} a_i \cdot (x-c_1) \cdot (\sum _{j=0}^{i-1} x^j \cdot {c_1}^{i-1-j})</cmath>
 +
 +
<cmath>=(x-c_1) \cdot g(x)</cmath>
 +
 +
for a (n-1)th degree polynomial <math>g(x)</math> with leading coeficient <math>a_{n}</math>. Then <math>g(x)</math> satisfy the conditions of the inductive hypothesis.
 +
 +
Now, let <math>k</math> be an arbitary integer with <math>1 \le k \le n+1</math>. <math>f(c_k) \equiv 0 \equiv f(c_i) \pmod {p}</math>. Thus,
 +
 +
<cmath>0 \equiv f(c_k) - f(c_1) = (c_k-c_1) g(c_k) \pmod {p}</cmath>
 +
 +
<cmath>\implies g(c_k) \equiv 0 \pmod {p}</cmath>
 +
 +
since
 +
 +
<cmath>c_k \not\equiv c_1 \pmod {p}</cmath>
 +
 +
Thus <math>c_2 , c_2 , \dots , c_{n+1}</math> are all roots of <math>g(x)</math>. This contradicts the inductive hypothesis, and thus establishes the lemma. <math>\square</math>.
 +
 +
 +
Now, we have a useful corollary:
 +
 +
 +
'''Corollary (Lemma 2):'''
 +
 +
Let <math>p</math> be prime and let <math>d</math> be a divisor of <math>p-1</math>. Then the polynomial <math>x^d -1</math> have exactly <math>d</math> incongruent roots modulo <math>p</math>.
 +
 +
 +
''Proof:'' Let <math>p-1 =d \cdot e</math>. We have
 +
 +
<cmath>x^{p-1} -1= (x^d-1) g(x)</cmath>
 +
 +
for a <math>p-1-d</math> degree polynomial <math>g(x)</math>. By Fermat's Little Theorem, <math>x^{p-1}-1</math> have exactly <math>p-1</math> roots modulo <math>p</math>. By Lagrange's Theorem, <math>g(x)</math> have at most <math>p-d-1</math> incongruent roots modulo <math>p</math>. Thus, <math>x^d -1</math> have at least <math>d</math> roots modulo <math>p</math>. On the other hand, Lagrange's Theorem again implies <math>x^d -1</math> have at ''most'' <math>d</math> incongruent roots. Thus, <math>x^d -1</math> have exactly <math>d</math> roots. <math>\square</math>
 +
 +
 +
This result can be used to prove a result regarding the number of integer of a certain integer a prime <math>p</math> can have. Before we state and prove that, we present yet another lemma.
 +
 +
 +
'''Lemma 3:'''
 +
 +
Let <math>p</math> be prime and let <math>d</math> be a divisor of <math>p-1</math>. Then the number of positive integers less than <math>p</math> of order <math>d</math> modulo <math>p</math> do not exceed <math>\phi (d)</math>.
 +
 +
 +
''Proof:'' Let <math>F(d)</math> denote the number of positive integers less than <math>p</math> of order <math>d</math> modulo <math>p</math>.
 +
 +
Now, if <math>F(d)=0</math>, the result is trivial. Assume <math>F(d) \ne 0</math>, and that <math>a</math> is an integer with order <math>d</math> modulo <math>p</math>. Then the integers
 +
 +
<cmath>a, a^2, \dots , a^d</cmath>
 +
 +
are incongruent modulo <math>p</math>. Also, each of those integers are a root of <math>x^d-1</math>. By Lemma 3, those are the only roots. Thus, every possible integer with order <math>d</math> modulo <math>p</math> must be a power of <math>a</math>. Obviously, the exponent of <math>a</math> must be relatively prime to <math>d</math>, or otherwise there exist a smaller solution to <math>(a^k)^x \equiv 1 \pmod {p}</math> (for <math>x</math>) than <math>d</math>, which would cause <math>\text {ord} _d a^k</math> to be less than <math>d</math>. Therefore, the result follow by the definition of the Euler-Phi Function. <math>\square</math>.
 +
 +
 +
In fact, the number of positive integers less than <math>p</math> of order <math>d</math> modulo <math>p</math> is ''exactly'' <math>\phi (d)</math>, as the following lemma shows:
 +
 +
 +
'''Lemma 4:'''
 +
 +
Let <math>p</math> be prime and let <math>d</math> be a divisor of <math>p-1</math>. Then the number of positive integers less than <math>p</math> of order <math>d</math> modulo <math>p</math> is exactly <math>\phi (d)</math>.
 +
 +
 +
''Proof:'' As the page [[Proof of Some Primitive Roots Facts]] proved, the order of an integer modulo <math>p</math> divides <math>p-1</math>, we have
 +
 +
<cmath>\sum _{d|p-1} F(d) = p-1</cmath>
 +
 +
By some Euler-Phi Function facts, we know that
 +
 +
<cmath>\sum _{d|p-1} \phi (d) = p-1</cmath>
 +
 +
Lemma 3 implies <math>F(d) \le \phi (d)</math> for each <math>d|p-1</math>, so it follows that <math>F(d)= \phi (d)</math> for every <math>d</math>. <math>\square</math>.
 +
 +
 +
An easy corollary of that is when we take <math>d=p-1</math>, and we get that every prime have <math>\phi (p-1)</math> primitive roots. We have thus shown that every prime have a primitive roots.
 +
 +
Case 1 is completed.
 +
 +
===Case 2===
 +
 +
UNDER CONSTRUCTION

Revision as of 21:34, 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 easiest 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=240660"