Proof of the Existence of Primitive Roots

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

Next, we generalize case 1 and consider the case of $n$ being an arbitary power of a prime.

First, we consider the case where $n$ is a power of an odd prime. Powers of $2$ will be considered separately.

Now, we start by considering when $n$ is the square of an odd prime.

As the page Proof of Some Primitive Roots Facts shown, if $p$ is an odd prime, then $p^2$ have a primitive root. As it also shown, if $p$ have a primitive root and $p^2$ have a primitive root, then $p^k$ have a primitive root for all positive integers $k$ .

It follows that all prime powers (of odd primes) have a primitive root.

Next, we consider the case where $n$ is a power of $2$ . We conjecture that the only such $n$ with primitive roots are $2$ and $4$ only.

Theorem 1:

The only powers of $2$ with primitive roots are $2$ and $4$ .

Proof: Obviously, $2$ and $4$ have primitive roots. $1$ is a primitive root of $2$ and $3$ is a primitive root of $4$ .

Now, if $n \le 3$ , then we claim that $2^n$ have no primitive roots.

To see that, we claim that for all odd integers $a$ and positive integers $k$ greater than or equal to 3, we have

$a^{\frac{\phi (2^k)}{2}} = a^{2^{k-2}} \equiv 1 \pmod {2^k}$

To show that, we use mathematical induction. The case of $k=3$ is merely the fact that $x^2 \equiv 1 \pmod 8$ . Suppose

$a^{\frac{\phi (2^k)}{2}} = a^{2^{k-2}} \equiv 1 \pmod {2^k}$

There there exist a integer $d$ such that

$a^{2^{k-2}}=1+d \cdot 2^k$

Thus,

$a^{2^{k-1}}=1+d \cdot 2^{k+1} + d^2 \cdot 2^{2k}$

$\implies a^{2^{k-1}} \equiv 1 \pmod {2^{k+1}}$

which completes the inductive argument, which thus completes the theorem. $\square$ .

As the above have shown, all prime powers with primitive roots are

$2,4, \text {and } p^k$

where $p$ is an odd prime and $k$ is an positive integer.

This completes case 2.

Case 3

Now, we consider the case where $n$ is not a prime power. More specifically, we wish to show that if $n$ have a prime power and is not a prime power, then $n$ is twice a prime power.

Theorem 2:

If $n$ is a positive integer that is not a prime power or twice a prime power, then $n$ have no primitive roots.

Proof: Let $n$ have prime factorization

$n= {p_1}^{t_1} \cdot {p_2}^{t_2 } \cdot \dots \cdot {p_m}^{t_m}$

Suppose $n$ have a primitive root $r$ . Then Euler's Theorem shows that

$r^{\phi ({p_i}^{t_i})} \equiv 1 \pmod {{p_i}^{t_i}}$

so therefore

$r^{\text{lcm} ({p_1}^{t_1} , {p_2}^{t_2 } , \dots , {p_m}^{t_m})} \equiv 1 \pmod {n}$

Thus,

$\phi (n) = \text{ord} _{n} r \le \text{lcm} ({p_1}^{t_1} , {p_2}^{t_2 } , \dots , {p_m}^{t_m})$

It follows that

$\phi ({p_1}^{t_1}) , \phi ({p_2}^{t_2 } ), \dots , \phi ({p_m}^{t_m})$

are all pairwise relatively prime. However, this implies that there is at most one odd prime power. It follows that $n$ is either a prime power twice a prime power. $\square$

This completes the third (and last) case.

We have now shown that if $n$ have a primitive root, then $n$ is $2, 4$ , a prime power, or twice a prime power. The converse can easily be shown also. This, therefore, completes the proof. $\blacksquare$

Page

Toolbox

Search