5.3: Primitive Roots

\(\newcommand{\NN}{\mathbb N}\)
\(\newcommand{\RR}{\mathbb R}\)
\(\newcommand{\QQ}{\mathbb Q}\)
\(\newcommand{\ZZ}{\mathbb Z}\)
\(\newcommand{\Cc}{\mathcal C}\)
\(\newcommand{\Dd}{\mathcal D}\)
\(\newcommand{\Ee}{\mathcal E}\)
\(\newcommand{\Ff}{\mathcal F}\)
\(\newcommand{\Kk}{\mathcal K}\)
\(\newcommand{\Mm}{\mathcal M}\)
\(\newcommand{\Pp}{\mathcal P}\)
\(\newcommand{\ind}{\operatorname{ind}}\)
\(\newcommand{\ord}{\operatorname{ord}}\)

Now back to those elements which generate large cyclic subgroups – which have a name:

Definition: Primitive Root

Given \(n\in\NN\) such that \(n\ge2\), an element \(a\in(\ZZ/n\ZZ)^*\) is called a primitive root mod \(n\) if \(\ord_n(a)=\phi(n)\). We shall also call an integer \(x\in\ZZ\) a primitive root mod \(n\) if \([x]_n\) is a primitive root in the sense just defined.

Example \(\PageIndex{1}\)

From the two tables in the introduction to this chapter we can read off the following primitive roots mod their respective \(n\)’s:

Table 5.3.1: Primitive Roots for \(n=2,\dots,8,16,17\)

\(n\)	Primitive Roots mod \(n\)	\(\phi(n)\)	\(\phi(\phi(n))\)
2	1	1	1
3	2	2	1
4	3	2	1
5	2, 3	4	2
6	5	2	1
7	3, 5	6	2
8	none	4	2
⋮
16	none	8	4
17	3, 5, 6, 7, 10, 11, 12, 14	16	8

We have included the column of \(\phi(n)\) since that is the order that each primitive root must have. And then we added the column of \(\phi(\phi(n))\) as well, since by some strange magic it appears frequently to compute the number of primitive roots.

Let us state formally, and prove, the general result noticed in this example:

Theorem \(\PageIndex{1}\)

The probabilities assigned to events by a distribution function on a sample space are given by.

Proof

Given \(n\in\NN\) satisfying \(n\ge2\), if \(n\) has any primitive roots than it has exactly \(\phi(\phi(n))\) primitive roots.

Let \(a\in(\ZZ/n\ZZ)^*\) be a primitive root. That means that \[\left<a\right>=\left\{a,\ a^2,\ \dots\ a^{\ord_n(a)}\right\}=(\ZZ/n\ZZ)^*\] since \(\ord_n(a)=\phi(n)=\#\left((\ZZ/n\ZZ)^*\right)\). Any other primitive root \(b\), being an element of \((\ZZ/n\ZZ)^*\) must be one of these powers of \(a\). In other words, \(\exists k\in\NN\) such that \(b=a^k\).

In order for this \(b\) to be a primitive root, its order must be \(\phi(n)\). But from Theorem 5.1.3, we know that \[\ord(b)=\frac{\ord(a)}{\gcd(\ord(a),k)}=\frac{\phi(n)}{\gcd(\phi(n),k)}\ .\] Therefore \(b=a^k\) will be a primitive root if and only if \(\gcd(\phi(n),k)=1\). From the definition of Euler’s \(\phi\) function, this happens for exactly \(\phi(\phi(n))\) values of \(k\).

Let’s see if we can prove that in some circumstances, we will have the first primitive root that the above theorem requires. The easiest situation in which that might happen will probably be when the modulus is prime, as we have the strongest tools to work with in that case.

Finding elements of a particular order \(d\) amounts (in part) to finding solutions to the equation \(x^d-1\equiv0\pmod{p}\). The first step toward this is the following more general theorem about polynomials in mod \(p\) due to Lagrange:

Theorem \(\PageIndex{2}\)

For \(n\in\NN\) and \(a_0,\dots,a_n\in\ZZ\), the polynomial \[a_nx^n+\dots+a_1x+a_0\equiv0\pmod{p}\ ,\] where \(a_n\not\equiv0\pmod{p}\), has at most \(n\) solutions in \(\ZZ/p\ZZ\) if \(p\) is prime.

Proof

We use induction on the degree \(n\). The base case \(n=1\) amounts to solving the linear congruence \(a_1x+a_0\equiv0\pmod{p}\) where \(a_1\not\equiv0\pmod{p}\). Since \(p\) is prime, this means that \(\gcd(p,a_1)=1\), and therefore the linear congruence has a unique solution mod \(p\) by the version of Theorem 2.2.2 as stated in the Note in Chapter 2.2.

Now for the inductive step, assuming that the theorem is true for some \(n\in\NN\), we shall prove it for the case \(n+1\). So let \(a_0,\dots,a_{n+1}\in\ZZ\) be such that \(a_{n+1}\not\equiv0\pmod{p}\). If \[a(x)=a_{n+1}x^{n+1}+a_nx^n+\dots+a_1x+a_0\] has no zeros in mod \(p\), then the theorem is certainly true for this polynomial of degree \(n+1\): the number of solutions to \(a(x)\equiv0\pmod{p}\) is \(0<n+1\).

If instead \(a(x)\) has at least one zero \(z_1\) in mod \(p\), do long division of polynomials to get \[a(x)=b(x)(x-z_1) + r(x)\] where \(b(x)\) and \(r(x)\) are polynomials with integral coefficients and such that \[0\le\deg(r(x))<\deg(x-z_1)=1\ .\] It therefore follows that \(r(x)\) is a constant polynomial, say with value \(r_1\in\ZZ\).

Plug \(z_1\) into the above formula resulting from division of polynomials to get \[0\equiv a(z_1)\equiv b(z_1)(z_1-z_1)+r_1\equiv r_1\pmod{p}\ .\] Hence \(r_1\equiv0\pmod{p}\), which means that our polynomial \(a(x)\equiv b(x)(x-z_1)\pmod{p}\). But \(a_{n+1}\) equals (one times) the leading coefficient of \(b(x)\), so that leading coefficient must not be congruent to \(0\) mod \(p\).

Hence the inductive hypothesis applies to \(b(x)\) and tells us that it has no more than \(n\) roots in mod \(p\). These roots of \(b(x)\), plus the single root of \((x-z_1)\), total no more than \(n+1\) roots for \(a(z)=b(x)(x-z_1)\).

All we need to do to finish is to see that any root of \(a(x)\) must in fact be a root of \(b(a)\) or \((x-z_1)\). So suppose \(r\in\ZZ\) is a root, so \[a(r)=b(r)(r-z_1)\equiv0\pmod{p},\] which means in turn that \(p\mid b(r)(r-z_1)\). Then by Proposition 3.1.1 we must have \(p\mid b(r)\) or \(p\mid(r-z_1)\). In other words, \(b(r)\equiv0\pmod{p}\) or \((r-z_1)\equiv0\pmod{p}\), as we hoped. [This amounts to using what is called in basic algebra the “zero product property”, which is true in \(\ZZ/p\ZZ\) for \(p\) prime by Proposition 3.1.1; in abstract algebra, we say that \(\ZZ/p\ZZ\) is a domain if \(p\) is prime.]

Thus the roots of \(a(x)\) all come from roots of \(b(x)\) or \((x-z_1)\), and so number at most \(n+1\), which means we have proven the inductive step.

So much for a maximum number of roots. In the following particular case, we can get the exact number of roots:

Theorem \(\PageIndex{3}\)

If \(p\) is prime and \(d\mid p-1\), then there are exactly \(d\) solutions, up to congruence mod \(p\), of the congruence \[x^d=1\pmod{p}\ .\]

Proof

Let \(p\) and \(d\) be as in the statement, and define \(m=(p-1)/d\in\NN\). We use a clever factorization, defining \[\begin{aligned} a(x)&=x^d-1,\\ b(x)&=x^{dm-d}+x^{dm-2d}+\dots+x^d+1,\ \text{and}\\ c(x)&=x^{p-1}-1\end{aligned}\] so that \(c(x)=a(x)b(x)\).

Notice that by Fermat’s Little Theorem, \(c(x)\) has exactly \(p-1\) roots which are distinct in mod \(p\), being \(\{1,\dots,p-1\}\). Also, by the previous Theorem 5.3.2, \(b(x)\) has at most \(\deg(b(x))=dm-d=p-1-d\) roots. Since, as in the proof of that Theorem 5.3.2 (the part where we mentioned the “zero product property”), roots of \(c(x)\) correspond exactly to the roots of \(a(x)\) and those of \(b(x)\), there must be at least \(d\) roots of \(a(x)\) to add to these no more than \(p-1-d\) roots of \(b(x)\), making the exactly \(p-1\) roots of \(p-1\).

We are now in a position to quantify exactly the congruence classes in \(\ZZ/p\ZZ\), for \(p\) a prime, of particular orders:

Theorem \(\PageIndex{4}\)

If \(p\) is prime and \(d\mid p-1\), then there are exactly \(\phi(d)\) distinct congruence classes of order \(d\) in \(\ZZ/p\ZZ\).

Proof

Let \(p\) and \(d\) be as in the statement and write \[\psi(k)=\#\left(\left\{\ell\in\ZZ\mid1\le\ell\le p-1\text{ and }\ord_p(\ell)=k\right\}\right)\ .\] By our version of Lagrange’s Theorem 3.3.1, any \(\ell\in\ZZ\) such that \(1\le\ell\le p-1\) has an order which divides \(\phi(p)=p-1\), so \[\sum_{\substack{k\in\NN\\s.t.\ k\mid p-1}} \psi(k) = p-1\ .\] In addition, by Gauss’s Theorem 5.2.1, \[\sum_{\substack{k\in\NN\\s.t.\ k\mid p-1}} \phi(k) = p-1\ .\]

Therefore \[\sum_{\substack{k\in\NN\\s.t.\ k\mid p-1}} \phi(k) = \sum_{\substack{k\in\NN\\s.t.\ k\mid p-1}} \psi(k)\ .\] Our goal now is to show that \(\forall k\in\NN\) such that \(k\mid p-1\), we have \(\psi(k)\le\psi(k)\). If we can do this, then in fact for all such \(k\), we would have to have \(\psi(k)=\psi(k)\) because if for one \(k\) we had \(\psi(k)<\psi(k)\) then there would be no way for another \(k\) to give \(\psi(k)>\psi(k)\) so that \(\sum\psi(k)=\sum\phi(k)\) could still hold.

So let \(k\in\NN\) satisfy \(k\mid p-1\). If \(\psi(k)=0\), meaning that there are no elements of order \(k\), then certainly \(\psi(k)\le\phi(k)\) as \(\phi(k)\) is a non-negative function.

Suppose \(\psi(k)>0\), meaning there exists at least one element, call it \(a\), of order \(k\) in \(\ZZ/p\ZZ\). Notice that for any \(n\in\NN\), \((a^n)^k=(a^k)^n\equiv1^n\equiv1\pmod{p}\), which means that \(a,\dots,a^k\) are distinct elements of \(\ZZ/p\ZZ\) which all satisfy \[x^k-1\equiv1\pmod{p}\ .\] By Theorem 5.3.5, there are exactly \(k\) solutions of this congruence equation. These solutions include all of the elements of \(\ZZ/p\ZZ\) of order \(k\), and maybe other elements, whose order is a divisor of \(k\), in which we are not so interested.

But in fact, by Theorem 5.1.3, we know exactly the orders of these elements \(a,\dots,a^k\): the order of \(a^\ell\) is \[\frac{\ord_p(a)}{\gcd(\ord_p(a),\ell)}=\frac{k}{\gcd(k,\ell)}\ .\]

Thus the elements of \(\ZZ/p\ZZ\) of order \(k\) are those elements \(a^\ell\) for \(\ell\in\ZZ\) satisfying \(1\le\ell\le k\) for which \(\gcd(k,\ell)=1\). There are therefore \(\phi(k)\); in other words, \(\psi(k)=\phi(k)\).

So, the punch line:

Corollary \(\PageIndex{1}\)

If \(p\) is prime, there are \(\phi(p-1)\) primitive roots in \(\ZZ/p\ZZ\).

Proof

Use \(k=p-1\) in the previous theorem

Just to finish the thread of conjectures with which we started this chapter and section, let us prove the

Theorem \(\PageIndex{5}\)

Let \(k\in\NN\) satisfy \(n\ge3\). Then \(n=2^k\) has no primitive roots.

Proof

We shall prove that for all odd numbers \(a\), \[a^{2^{k-2}}\equiv1\pmod{2^k}\] by induction on \(k\).

Start with \(k=3\) and just look at all the congruence classes in \(\ZZ/8\ZZ\) with odd representatives, and the squares of these classes: \[[1]_8^2=[1]_8,\qquad[3]_8^2=[9]_8=[1]_8,\qquad[5]_8^2=[25]_8=[1]_8, \;\;\;\;\text{ and }\;\;\;\;[7]_8^2=[49]_8=[1]_8\ .\] So the base case \(k=3\) is established.

Now assume the statement holds for the value \(k\), meaning that for all odd \(a\), \[a^{2^{k-2}}\equiv1\pmod{2^k}\ .\] In other words, \(\exists\ell\in\ZZ\) such that \[a^{2^{k-2}}=2^k\ell+1\ .\] Squaring both sides of this, we get \[a^{2^{k-1}}=\left(a^{2^{k-2}}\right)^2=\left(2^k\ell+1\right)^2= 2^{2k}\ell^2+2\cdot2^k\ell+1=2^{k+1}\left(2^{k-1}\ell^2+\ell\right)+1,\] meaning that \[a^{2^{(k+1)-2}}=a^{2^{k-1}}\equiv1\pmod{2^{(k+1)}}\ .\]

The inductive proof of the statement with which we began this proof is done. But notice that this means that for all odd numbers \(a\), or, otherwise, for all \(a\in(\ZZ/2^k\ZZ)^*\), \(\ord_{2^k}(a)\le2^{k-2}<2^{k-1}\). Thus \(n=2^k\) has no primitive roots, which would all have to be odd numbers of order \(\phi(2^k)=2^{k-1}\).

As we thought we noticed, based on the few examples we had calculated, large powers of two do not have primitive roots.

Exercise \(\PageIndex{1}\)

1. Express each of the primitive roots of \(17\) as a power of one of them.
2. Find all of the primitive roots for the primes \(11\) and \(13\) and express them each as a power of one of them.
3. Find all of the elements of \(\ZZ/13\ZZ\) which have each possible order.
4. By expressing everything as powers of single primitive root, use Corollary 5.3.1 to prove one direction of Wilson’s Theorem
5. If \(r\) is a primitive root of the odd prime \(p\), prove that \(r^{(p-1)/2}\equiv-1\pmod{p}\). Also, prove that if \(s\) is any other primitive root of \(p\), then \(rs\) cannot be a primitive root.
6. Prove that the inverse of a primitive root is always a primitive root.
7. If \(p\) is a prime congruent to \(1\mod{4}\), prove that for all primitive roots \(r\) of \(p\), \(-r\) is also a primitive root. If instead \(p\) is a prime congruent to \(3\mod{4}\), prove that \(\ord_p(-r)=(p-1)/2\).