A Kick in the Discovery

It’s been a while since we’ve added to the Newbie at Number Theory series. Even so, the series is not complete yet! There are a few gaping holes between what we have covered thus far and what I would like to cover before completing the series. Today we will be covering one of the missing topics: the concept of primitive roots. Knowing what they are, that they exist in the first place, and how to use them will make primitive roots an indispensable tool for us as number theorists.

We will begin with some observations meant to motivate the discovery of what we will eventually call primitive roots. Our goal is to ultimately prove that every prime has primitive roots. With this aim, we will first discover and prove results concerning the order of an integer modulo a prime. Finally, we prove a key theorem known as Lagrange’s Theorem (not the one from group theory!). This will then culminate in a proof that primes have primitive roots.

Let’s get into it!

Remark: Just to lay all the cards down, this article will assume that you are familiar with induction, modular arithmetic, Fermat’s Little Theorem, Euler’s totient function, and lastly, Gauss’s Theorem. All of which can be found in the Newbie at Number Theory series.

Outline of Awesomeness

Motivation

Let’s begin with an observation.

What’s your favorite small prime (greater than 2 to make it interesting)? Seven! Great choice. Let’s consider powers of the integers modulo 7.

Where the 1’s in the rightmost column are blue to indicate that all integers relatively prime to 7 when raised to the $7-1=6^{th}$ power are congruent to 1, by Fermat’s Little theorem.

A potentially interesting observation is that there are two numbers, $3$ and $5,$ that run through all the residue classes modulo $7.$ That is, $3^k$ is congruent to $1, 2, 3, 4, 5, 6$ for some positive integer $k.$ Likewise for $5^k.$

This is interesting because we know that we can get to all the integers: $1, 2, 3, 4, 5, 6 \;(\mathrm{mod}\;7),$ by starting with $1$ and then simply adding $1$ to itself:

In this manner, $1$ generates all the residue classes modulo any number using addition. What our observation about the numbers $3$ and $5$ modulo $7$ tells us is that they generate all the residue classes modulo $7$ using exponentiation (i.e., multiplication). For instance, take $3$ and raise it to multiple powers, and we get the same list of integers (after reducing modulo $7$)

Although not in order.

Question: Do numbers like this always exist for prime numbers?

Let’s test some other small primes:

So, for at least some of the smallest prime numbers, there do exist these special numbers that run through all the residue classes. We call these numbers primitive roots of the prime $p.$

There is a `better way’ to look at primitive roots, and it introduces the notion of the order of a number modulo $p.$

Primitive Roots and the Order of a Number

The Order of a Number

Definition (Order of an Integer): Let $p$ be a prime. An integer $a$ has order $k,$ if $k$ is the smallest positive integer such that $a^k\equiv 1\;(\mathrm{mod}\;p).$

We denote the order of $a$ modulo $p$ by $\mathrm{ord}_p{(a)}.$ When the context is clear we will drop the subscript and write $\mathrm{ord}{(a)}.$

Remark 1: Note, by Fermat’s Little Theorem, we know that $1\leq \mathrm{ord}_p{(a)}\leq p-1$ when $a\not\equiv 0 \;(\mathrm{mod}\;p).$

Remark 2: We will be concerning ourselves here exclusively with numbers that are relatively prime to whatever prime we are working with. But to be complete, if $p\mid a,$ then there is no power such that $a^k\equiv 1\;(\mathrm{mod}\;p).$ So, we say that $a$ has order infinity and write $\mathrm{ord}_p{(a)} = \infty.$

Challenge: Can you prove that $\mathrm{ord}{(a)}=1$ if and only if $a\equiv 1\;(\mathrm{mod}\;p)?$Give it a go!

Example (Working modulo 7): (Click in the Discovery)

Let’s continue to work modulo 7. Then, the order of the integers 1 through 6 are

$\mathrm{ord}_7{(1)}=1\\ \mathrm{ord}_7{(2)}=3 \\ \mathrm{ord}_7{(3)}=6 \\ \mathrm{ord}_7{(4)}=3 \\ \mathrm{ord}_7{(5)}=6 \\ \mathrm{ord}_7{(6)}=2.$

Example (Working modulo 11): (Click in the Discovery)

Let’s try to work modulo 11. Then, the order of the integers 1 through 10 are

$\mathrm{ord}_{11}{(1)}=1\\ \mathrm{ord}_{11}{(2)}= 10 \\ \mathrm{ord}_{11}{(3)}=5 \\ \mathrm{ord}_{11}{(4)}=5 \\ \mathrm{ord}_{11}{(5)}=5 \\ \mathrm{ord}_{11}{(6)}=10 \\ \mathrm{ord}_{11}{(7)}=10\\ \mathrm{ord}_{11}{(8)}=10 \\ \mathrm{ord}_{11}{(9)}=5 \\ \mathrm{ord}_{11}{(10)}=2.$

Order lets us succinctly define what a primitive root is.

Primitive Roots

Definition (Primitive Roots): Let $p$ be a prime. An integer $a,$ with order $p-1$ modulo $p,$ is called a primitive root of $p.$

For example, we would say $3$ and $5$ are primitive roots modulo $7$ since $\mathrm{ord}_7{(3)} = \mathrm{ord}_7{(5)} = 6.$

Now it’s not a priori obvious why this definition jives with the property that we observed at the beginning. More precisely, we were working with the observation that $3^k$ runs through all the integers $1, 2, 3, 4, 5, 6 \;(\mathrm{mod}\;7)$ as we change $k.$ Our definition only talks about one power of $3,$ i.e., $k=\mathrm{ord}_7{(3)} = 6.$ However, we will see in our next proposition that the two ideas are the same!

Proposition (Jiving Concepts): Let $p$ be a prime. Then, $a$ is a primitive root of $p$ if and only if $a, a^2,\cdots, a^{p-1}$ run through the residue classes modulo $p.$ I.e., $a, a^2,\cdots, a^{p-1}$ run through the numbers $1,2,\cdots, p-1$ but not necessarily in that order.

Example (Working modulo 7): (Click in the Discovery)

Recall that $\mathrm{ord}_7{(3)} = 6$ so that $3$ is a primitive root of $7,$ by definition. Furthermore, by our observations at the beginning, we have

$$3,\, 3^2,\, 3^3,\, 3^4,\,3^5 ,\, 3^6 \equiv 3,\, 2 ,\,6,\,4,\,5,\,1 \;\; (\mathrm{mod}\;7)$$

So that the powers of $3$ run through the integers $1,2,\cdots, 6$ modulo $7.$

Proof: (Click in the Discovery)

Let $p$ be a prime and note that $a\not\equiv 0 \;(\mathrm{mod}\;p).$

Forward: If $a$ is a primitive root of $p,$ then $a, a^2,\cdots, a^{p-1}$ run through the residue classes modulo $p.$

Let $a$ be a primitive root of $p.$ Consider the powers $a, a^2,\cdots, a^{p-1}.$ We want to show they are all distinct modulo $p.$ To do so, we proceed by contradiction. Suppose that $a^n\equiv a^m \;(\mathrm{mod}\;p)$ for $1\leq m < n \leq p-1.$ It follows, $a^{n-m}\equiv 1 \;(\mathrm{mod}\;p)$ where $1\leq n-m\leq p-2.$ However, this is a contradiction, since $a$ is a primitive root of $p,$ and hence $\mathrm{ord}_p{(a)}=p-1>n-m.$

Consequently, $a, a^2,\cdots, a^{p-1}$ runs through the residue classes modulo $p.$

Backward: If $a, a^2,\cdots, a^{p-1}$ run through the residue classes modulo $p,$ then $a$ is a primitive root of $p.$

Let $a, a^2,\cdots, a^{p-1}$ run through all the residue classes modulo $p.$ We will show that $\mathrm{ord}_p{(a)}=p-1.$ Indeed, suppose that $\mathrm{ord}_p{(a)}=d$ where $1\leq d\leq p-2.$ If $d=1,$ then $a=1$ contradicting that $a, a^2,\cdots, a^{p-1}$ run trhough all the residuce classes modulo $p.$ So, $a> 1.$

Since $a^{d}\equiv 1 \;(\mathrm{mod}\;p),$ it follows $a^{d+1}\equiv 1a =a \;(\mathrm{mod}\;p).$ That is, $a \equiv a^{d+1}\ \;(\mathrm{mod}\;p)$ for $2\leq d+1\leq p-1.$ But, this contradicts that $a, a^2,\cdots, a^{p-1}$ run trhough all the residuce classes modulo $p.$

Thus, $a$ is a primitive root of $p.$

Another Observation Regarding Orders

Question for you: What is the order of $5$ and $10$ modulo $19?$ And, is either of them a primitive root of $19?$ (Click in the Discovery)

So the order of $5$ is the smallest positive integer, $k,$ such that $5^k\equiv 1\;(\mathrm{mod}\;19).$ Likewise, the order of $10$ is the smallest positive integer, $k,$ such that $10^k\equiv 1\;(\mathrm{mod}\;19).$

A `quick’ computation gives,

Thus, $\mathrm{ord}_{19}{(5)}=9$ and $\mathrm{ord}_{19}{(10)}=18$ which means that $10$ is a primitive root of $19.$

Did you notice anything about the previous examples given thus? Go take a look at what orders were present for different primes.

---

Well, when working modulo $7,$ the only possible orders were $1, 2, 3,$ and $6.$ And, when working modulo $11,$ the only orders were $1, 2, 5,$ and $10.$ Suspicious huh? It seems like the possible orders are the divisors of $p-1.$ In fact, this is better stated as: It seems like the possible orders are the divisors of $\phi(p) =p-1.$ Where $\phi(p)$ is Euler’s Totient function. In fact, this is indeed the case! We’ll see in just a moment why this happens, but it is worth remarking that this wonderful observation is just the tip of a deep result of group theory known as Lagrange’s theorem (group theory). Note: this is not Lagrange’s theorem we will see below; this is a different theorem from Lagrange that relates to group theory.

Proposition (Order Restrictions): Let $p$ be a prime. Then the order of any integer $a\not\equiv 0 \;(\mathrm{mod}\;p)$ divides $p-1.$ That is, $\mathrm{ord}{(a)}\mid p-1.$

Proof: (Click in the Discovery)

Let $p$ be a prime, $a\not\equiv 0 \;(\mathrm{mod}\;p),$ and $\mathrm{ord}{(a)}=d.$ Suppose that $d\nmid p-1.$ That is, $p-1 = dk + r$ for integers $k$ and $r$ such that $1 \leq r < d.$ (This is the division algorithm). By Fermat’s Little theorem, we know that $a^{p-1}\equiv 1\;(\mathrm{mod}\;p).$ Thus,

$$a^{p-1}= a^{dk+r}\equiv1\;(\mathrm{mod}\;p).$$

With some exponent algebra and that $\mathrm{ord}{(a)}=d,$

$$a^{dk+r}=(a^{d})^ka^r\equiv 1^ka^r \equiv a^r \equiv 1\;(\mathrm{mod}\;p).$$

Thus, $a^r \equiv 1\;(\mathrm{mod}\;p)$ contradicting that $\mathrm{ord}{(a)}=d.$

We are now ready to show that every prime number has a primitive root!

All Primes Have Them!

The Proof- Step 1: Lagrange’s Theorem

This proof will end up with two theorems and two corollarys.

Theorem (Lagrange’s Theorem): Let $p$ be a prime and consider the polynomial

$$f(x) = a_n x^n + a_{n-1}x^{n-1}+\cdots + a_1x +a_0$$

where $a_0,a_1,\cdots,a_n \in \Z$ and $a_n\not\equiv 0 \;\;(\mathrm{mod}\;p).$ That is, the degree of $f(x)$ equals $n.$ Then, the congruence

$$\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad f(x) \equiv 0 \;\; (\mathrm{mod}\;p) \qquad\qquad\qquad\qquad\qquad\qquad \qquad\qquad\qquad(\smiley)$$

has at most $n$ solutions modulo $p.$ That is, $n$ incongruent solutions modulo $p.$

Remark: Note how this contrasts with the fundamental theorem of algebra, which states: Every polynomial of degree $n$ has exactly $n$ solutions, with multiplicity.

Proof: (Click in the Discovery)

Key Idea: What we want to do is use induction on the degree of the polynomial. To connect higher degree polynomials to lesser degree polynomials, we use polynomial long division (see here or here for a refresher on polynomial long division).

Beginning of Proof:

Base Case $(n=1):$ To begin, recall that we’ve shown that linear congruences such as $ax\equiv b\;\;(\mathrm{mod}\;p)$ have one unique solution modulo $p$ when $a\not\equiv 0 \;(\mathrm{mod}\;p),$ see here. Thus, all we need to do is use $a=a_1$ and $b=-a_0.$

Inductive Hypothesis: Now let’s assume that Lagrange’s theorem holds for all polynomials whose degree is equal to $k-1.$

Induction Step: Consider now the degree $k$ polynomial,

$$f(x) = a_k x^k + a_{k-1}x^{k-1}+\cdots + a_1x +a_0 \,, \qquad \qquad a_k\not\equiv 0 \;(\mathrm{mod}\;p) .$$

It’s possible that $f(x) \not\equiv 0 \;\;(\mathrm{mod}\;p)$ for all $x,$ and thus $(\smiley)$ has no solutions. In which case, we’re done! On the other hand, suppose $f(x)$ has at least one solution, denoted $x_*.$ Using polynomial division, we have

$$f(x) = (x-x_*) g(x) + r(x),$$

where $g(x)$ is a degree $k-1$ polynomial and $r(x) \in \Z$ is an integer (this follows from the division algorithm for polynomials, see Remainder Theorem here). Let $R= r(x) \in \Z.$ In particular, we have

$$f(x) = (x-x_*) g(x) + R,\;\;\mathrm{where}\; \deg{(g)}=k-1\;\mathrm{and}\; R\in \Z.$$

We claim that $R\equiv 0\;(\mathrm{mod}\;p).$ Indeed, first observe $f(x_*) = (x_*-x_*) g(x_*)+R \equiv 0 \;(\mathrm{mod}\;p).$ But, $(x_*-x_*) g(x_*)=0$ so that $R \equiv 0 \;(\mathrm{mod}\;p)$ as claimed.

In summary, thus far, we have

$$f(x) \equiv (x-x_*) g(x) \;\; (\mathrm{mod}\;p),\;\;\;\;\;\;\mathrm{where}\; \deg{(g)}=k-1.$$

Now, we are in a perfect situation to use our induction hypothesis! We conclude that $g(x)$ has at most $k-1$ solutions to the congruence $g(x) \equiv 0 \;\; (\mathrm{mod}\;p).$ Hence, $f(x)$ has at most $k$ solutions since any solution $y_*$ of $g(x) \equiv 0 \;\; (\mathrm{mod}\;p),$ will also satisfy $f(x) \equiv 0 \;\; (\mathrm{mod}\;p),$ by the following observation:

$$f(y_*) \equiv (y_*-x_*) g(y_*) \equiv (y_*-x_*)\cdot 0 \equiv 0\;\; (\mathrm{mod}\;p).$$

Thus concluding the proof.

Now we need a stronger result for a very specific polynomial.

Corollary: Let $p$ be a prime. If $d\mid p-1,$ then the congruence $x^d -1 \equiv 0 \;\;(\mathrm{mod}\;p)$ has exactly $d$ solutions.

Proof: (Click in the Discovery)

By Lagrange’s Theorem, we know that $x^d -1 \equiv 0 \;\;(\mathrm{mod}\;p)$ has at most $d$ solutions. Thus, all we must do is find all those solutions.

To begin, recall Fermat’s little theorem tells us that the congruence $x^{p-1} -1 \equiv 0 \;\;(\mathrm{mod}\;p)$ has exactly $p-1$ incongruent solutions. That is, $1,\,2,\,\cdots,p-1$ are all solutions to $x^{p-1} -1 \equiv 0 \;\;(\mathrm{mod}\;p).$

Let’s now factor $x^{p-1} -1$ into a particularly useful form for us. Using that $d\mid p-1$ we have $p-1 = dk$ for some $k\in \Z.$ Consequently, the following factorization falls out,

$$x^{p-1} -1 = \Big(x^d-1\Big)\cdot \Big( x^{d(k-1)} + x^{d(k-2)}+\cdots + x^{d}+1 \Big).$$

Observe that the polynomial $x^{d(k-1)} + x^{d(k-2)}+\cdots + x^{d}+1$ has degree $d(k-1) = dk-d = p-1 -d$ and has integer coeffients. Thus, by Lagrange’s theorem, $x^{d(k-1)} + x^{d(k-2)}+\cdots + x^{d}+1 \equiv 0 \;\;(\mathrm{mod}\;p)$ has at most $p-1-d$ solutions. Furthermore, recall that we already concluded that the polynomial $x^d -1 \equiv 0 \;\;(\mathrm{mod}\;p)$ has at most $d$ solutions.

$$\mathrm{Summary}: \qquad \begin{matrix} x^{d(k-1)} + x^{d(k-2)}+\cdots + x^{d}+1 \equiv 0 \;\;(\mathrm{mod}\;p) \;\;\mathrm{has} \;\mathrm{at}\;\mathrm{most}\;p-1-d \;\mathrm{solutions} \\\\ x^d -1 \equiv 0 \;\;(\mathrm{mod}\;p) \;\;\mathrm{has} \;\mathrm{at}\;\mathrm{most}\;d \;\mathrm{solutions} \end{matrix}$$

Now note that the only way that the congruence $x^{p-1} -1 \equiv 0 \;\;(\mathrm{mod}\;p)$ has exactly $p-1$ solutions is if $x^d -1 \equiv 0 \;\;(\mathrm{mod}\;p)$ has exactly $d$ solutions and $x^{d(k-1)} + x^{d(k-2)}+\cdots + x^{d}+1 \equiv 0 \;\;(\mathrm{mod}\;p)$ has exactly $p-1-d$ soluions. Thus concluding our proof.

We are almost there! Woot!

Step 2 – Main Theorem

Theorem (Number of Integers with order $d\mid p-1$): Let $p$ be a prime and suppose that $d\mid p-1.$ Then, there are exactly $\phi(d)$ incongruent integers modulo $p$ that have order $d.$ Where $\phi(d)$ is Euler’s totient function.

Proof: (Click in the Discovery)

Let $p$ be a prime and suppose that $d\mid p-1.$ Furthermore, let $N(d)$ represent the number of incongruent integers, modulo $p,$ there are that have order $d.$ Thus, we want to show $N(d) = \phi(d).$

To begin, by Proposition (Order Restrictions) above, every integer’s order must divide $p-1.$ Consequently,

$$p-1 = \sum_{d\mid p-1} N(d).$$

Where the sum is done over the divisors of $p-1.$ See the footnote for an example.¹

By Gauss’s Theorem (see the theorem here), we have

$$p-1 = \sum_{d\mid p-1} N(d) =\sum_{d\mid p-1}\phi(d).$$

Recall that we are aiming to prove that $N(d) = \phi(d).$ To show this, we prove $N(d) \leq \phi(d)$ for all $d\mid p-1.$ Which, by the equality above implies $N(d) = \phi(d).$

Let $d\mid p-1.$

Case 1: $N(d) = 0.$ The result follows $0=N(d) \leq \phi(d).$

Case 2: $N(d)> 0.$ Then, there is some $a$ whose order is $d.$ Consider the following integers $a,\; a^2,\; \cdots a^{d}.$ They are all distinct by Proposition (Jiving Concepts), and they satify $x^d -1 \equiv 0 \;\;(\mathrm{mod}\;p)$ since $(a^n)^d – 1 = (a^d)^n -1 \equiv 1^n-1 = 0 \; \;\;(\mathrm{mod}\;p) .$ Furthermore, by the above corollary, they must be the only solutions to $x^d -1 \equiv 0 \;\;(\mathrm{mod}\;p).$ Thus, any integer with order $d$ must lie in the list $a,\; a^2,\; \cdots a^{d}.$ In particular, $a^{k}$ has order $d$ when $\gcd{(k,d)}=1.$ And there are $\phi(d)$ integers such that $\gcd{(k,d)}=1$ (by definition of Euler’s Totient function). Thus proving the claim.

Thus, we are done! Since as a quick corollary, we have:

All Primes Have Them!

Corollary: All primes have primitive roots.

Proof: A primitive root of $p-1,$ by definition, has order $p-1.$ By the previous theorem, there are $\phi(p-1)\geq 1$ primitive roots of $p.$ Let’s test this on the cases were $p=3,$ $p=5,$ and $p=7.$

Example (Working modulo 3, 5, and 7): (Click in the Discovery)

Recall the following tables:

Furthermore, we have $\phi(3-1)= 1,$ $\phi(5-1)= 2,$and $\phi(7-1)= 2.$ As our theorem asserts, there is one primitive root for $3,$and two primitive roots for $5$ and $7.$

Remark: Note how wonderful this result is. Not only do we know that all primes have primitive roots, but we also know how many they have, namely $\phi(p-1)$ of them! This is quite remarkable! Better yet, we also know how many numbers will have any order whatsoever! For instance, let’s take $p=7.$ How many numbers have order $5?$ Well, zero since $5\nmid (7-1),$ recall Proposition (Order Restrictions). What about how many numbers have order equal to $2?$The theorem tells us it should have $\phi(2) = 1.$ And, checking the following list we made earlier,

$\mathrm{ord}_7{(1)}=1\\ \mathrm{ord}_7{(2)}=3 \\ \mathrm{ord}_7{(3)}=6 \\ \mathrm{ord}_7{(4)}=3 \\ \mathrm{ord}_7{(5)}=6 \\ \mathrm{ord}_7{(6)}=2.$

We see that only $6$ has order $2.$

One more example: how many integers have order $5$ modulo $p=11?$ First off, $5\mid (11-1)$ so we can use our main theorem which tells us there are $\phi(5) = 4$ of them. Checking our list,

$\mathrm{ord}_{11}{(1)}=1\\ \mathrm{ord}_{11}{(2)}= 10 \\ \mathrm{ord}_{11}{(3)}=5 \\ \mathrm{ord}_{11}{(4)}=5 \\ \mathrm{ord}_{11}{(5)}=5 \\ \mathrm{ord}_{11}{(6)}=10 \\ \mathrm{ord}_{11}{(7)}=10\\ \mathrm{ord}_{11}{(8)}=10 \\ \mathrm{ord}_{11}{(9)}=5 \\ \mathrm{ord}_{11}{(10)}=2.$

we see that the four integers $3,\;4,\;5,$ and $9$ have order $5.$

Question: Can we predict which numbers will have what orders?

Other than a few special cases, such as $\mathrm{ord}_{p}{(a)}=1$ if and only if $a=1.$ Or, $\mathrm{ord}_{p}{(a)}=2$ if and only if $a=p-1,$ there is no sure-fire way to know what numbers have what order. For instance, we have no idea if $2$ is a primitive root for an infinite number of primes or not! Maybe you will figure this out!

See you next time!

I hope that you had some fun today! I have always found primitive roots to be a very fun topic. Especially how useful they are when proving a result known as Euler’s Criterion for quadratic residues, which we will cover next time. Another utility of learning about primitive roots and orders is that this concept shows up again in group theory. When I later learned about generators and orders in group theory, I found that I had a much better intuition for them because of topics covered in this article. I hope this is true for you too!

As always, leave questions in the comments!

Be Kind. Be Curious. Be Compassionate. Be Creative.

And Have Fun!

---

Footnotes:

1. Let $p=7.$ Then, $1,$ $2,$ $3,$ and $6$ are divisors of $p-1 = 6.$ Thus, we have
   $$\sum_{d\mid 6} N(d) = N(1)+ N(2) +N(3)+ N(6) .$$
   Which, using what we’ve computed earlier, we see equals $6 .$ ↩︎