5.2: Primitive Roots for Primes
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{\!\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
In this section, we show that every integer has a primitive root. To do this we need to introduce polynomial congruence.
Defintion: polynomial congruence
Let \(f(x)\) be a polynomial with integer coefficients. We say that an integer \(a\) is a root of \(f(x)\) modulo \(m\) if \(f(a)\equiv 0 (mod\ m)\).
Notice that \(x\equiv 3 (mod\ 11)\) is a root for \(f(x)=2x^2+x+1\) since \(f(3)=22\equiv 0(mod \ 11)\).
We now introduce Lagrange’s theorem for primes. This is modulo p, the fundamental theorem of algebra. This theorem will be an important tool to prove that every prime has a primitive root.
Lagrange’s Theorem
Let \[m(x)=b_nx^n+b_{n1}x^{n1}+...+b_1x+b_0\] be a polynomial of degree \(n, n\geq 1\) with integer coefficients and with leading coefficient \(b_n\) not divisible by a prime \(p\). Then \(m(x)\) has at most \(n\) distinct incongruent roots modulo \(p\).
Using induction, notice that if \(n=1\), then we have \[m(x)=b_1x+b_0 \ \ \mbox{and} \ \ p \nmid b_1.\] A root of \(m(x)\) is a solution for \(b_1x+b_0(mod \ p)\). Since \(p\nmid b_1\), then this congruence has exactly one solution by Theorem 26.
Suppose that the theorem is true for polynomials of degree \(n1\), and let \(m(x)\) be a polynomial of degree \(n\) with integer coefficients and where the leading coefficient is not divisible by \(p\). Assume now that \(m(x)\) has \(n+1\) incongruent roots modulo \(p\), say \(x_0,x_1,...,x_{n}\). Thus \[m(x_k)\equiv 0(mod \ p)\] for \(0\leq k\leq n\). Thus we have \[\begin{aligned} m(x)m(x_0)&=&b_n(x^nx_0^n)+b_{n1}(x^{n1}x_0^{n1})+...+b_1(xx_0) \\ &=& b_n(xx_0)(x^{n1}+x^{n2}x_0+...+xx_0^{n2}+x_0^{n1})\\&+& b_{n1}(xx_0)(x^{n2}+x^{n3}x_0+...+xx_0^{n3}+x_0^{n2})+...+b_1(xc_0)\\&=& (xx_0)f(x)\end{aligned}\] where \(f(x)\) is a polynomial of degree \(n1\) with leading coefficient \(b_n\). Notice that since \(m(x_k)\equiv m(x_0)(mod \ p)\), we have \[m(x_k)m(x_0)=(x_kx_0)f(x_k)\equiv 0(mod \ p).\] Thus \(f(x_k)\equiv 0(mod \ p)\) for all \(1\leq k\leq n\) and thus \(x_1,x_2,...,x_n\) are roots of \(f(x)\). This is a contradiction since we a have a polynomial of degree \(n1\) that has \(n\) distinct roots.
We now use Lagrange’s Theorem to prove the following result.
Consider the prime \(p\) and let \(p1=kn\) for some integer \(k\). Then \(x^n1\) has exactly \(n\) incongruent roots modulo \(p\).
Since \(p1=kn\), we have \[\begin{aligned} x^{p1}1&=&(x^n1)(x^{n(k1)}+x^{n(k2)}+...+x^n+1) \\&=&(x^n1)f(x)\end{aligned}\] By Fermat’s little theorem, we know that \(x^{p1}1\) has \(p1\) incongruent roots modulo \(p\). Also, roots of \(x^{p1}1\) are roots of \(f(x)\) or a root of \(x^n1\). Notice that by Lagrange’s Theorem, we have that \(f(x)\) has at most \(pn1\) roots modulo \(p\). Thus \(x^n1\) has at least \(n\) roots modulo \(p\). But again by Lagrange’s Theorem, since we have that \(x^n1\) has at most \(n\) roots, thus we get that \(x^n1\) has exactly \(n\) incongruent roots modulo \(p\).
We now prove a lemma that gives us how many incongruent integers can have a given order modulo \(p\).
Let \(p\) be a prime and let \(m\) be a positive integer such that \(p1=mk\) for some integer \(k\). Then \[S(m)=\{m:0<m<p, \ \ m \in \mathbb{Z} \}\leq \phi(m).\]
For each positive integer \(m\) dividing \(p1\),
Notice that if \(S(m)=0\), then \(S(m)\leq \phi(m)\). If \(S(m)>0\), then there is an integer \(a\) of order \(m\) modulo \(p\). Since \(ord_pa=m\), then \(a,a^2,...a^m\) are incongruent modulo \(p\). Also each power of \(a\) is a root of \(x^m1\) modulo \(p\) because \[(a^k)^m=(a^m)^k\equiv 1(mod \ p)\] for all positive integers \(k\). By Theorem 60, we know that \(x^m1\) has exactly \(m\) incongruent roots modulo \(p\), so that every root is congruent to one of these powers of \(a\). We also know by Theorem 57 that the powers of \(a^k\) with \((k,m)=1\) have order \(m\). There are exactly \(\phi(m)\) such integers with \(1\leq k \leq m\) and thus if there is one element of order \(m\) modulo \(p\), there must be exactly \(\phi(m)\) such positive integers less than \(p\). Hence \(S(m)\leq \phi(m)\).
In the following theorem, we determine how many incongruent integers can have a given order modulo \(p\). We actually show the existence of primitive roots for prime numbers.
Theorem
Every prime number has a primitive root.
Let \(p\) be a prime and let \(m\) be a positive integer such that \(p1=mk\) for some integer \(k\). Let \(F(m)\) be the number of positive integers of order \(m\) modulo \(p\) that are less than \(p\). The order modulo \(p\) of an integer not divisible by \(p\) divides \(p1\), it follows that \[p1=\sum_{m\mid p1}F(m).\] By Theorem 42, we see that \[p1=\sum_{m\mid p1}\phi(m).\] By Lemma 1, \(F(m)\leq \phi(m)\) when \(m\mid (p1)\). Together with \[\sum_{m\mid p1}F(m)=\sum_{m\mid p1}\phi(m)\] we see that \(F(m)=\phi(m)\) for each positive divisor \(m\) of \(p1\). Thus we conclude that \(F(m)=\phi(m)\). As a result, we see that there are \(p1\) incongruent integers of order \(p1\) modulo \(p\). Thus \(p\) has \(\phi(p1)\) primitive roots.
Exercises

Find the incongruent roots modulo 11 of \(x^2+2\).

Find the incongruent roots modulo 11 of \(x^4+x^2+1\).

Find the incongruent roots modulo 13 of \(x^3+12\).

Find the number of primitive roots of 13 and of 47.

Find a complete set of incongruent primitive roots of 13.

Find a complete set of incongruent primitive roots of 17.

Find a complete set of incongruent primitive roots of 19.

Let \(r\) be a primitive root of \(p\) with \(p\equiv 1(mod \ 4)\). Show that \(r\) is also a primitive root.

Show that if \(p\) is a prime and \(p\equiv 1(mod \ 4)\), then there is an integer \(x\) such that \(x^2\equiv 1(mod \ p)\).
Contributors
Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.