$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 5.2: Primitive Roots for Primes

[ "article:topic", "authorname:wraji", "Lagrange\u2019s theorem", "polynomial congruence", "showtoc:no" ]

$$\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_{n-1}x^{n-1}+...+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 $$n-1$$, 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^n-x_0^n)+b_{n-1}(x^{n-1}-x_0^{n-1})+...+b_1(x-x_0) \\ &=& b_n(x-x_0)(x^{n-1}+x^{n-2}x_0+...+xx_0^{n-2}+x_0^{n-1})\\&+& b_{n-1}(x-x_0)(x^{n-2}+x^{n-3}x_0+...+xx_0^{n-3}+x_0^{n-2})+...+b_1(x-c_0)\\&=& (x-x_0)f(x)\end{aligned} where $$f(x)$$ is a polynomial of degree $$n-1$$ 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_k-x_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 $$n-1$$ that has $$n$$ distinct roots.

We now use Lagrange’s Theorem to prove the following result.

Consider the prime $$p$$ and let $$p-1=kn$$ for some integer $$k$$. Then $$x^n-1$$ has exactly $$n$$ incongruent roots modulo $$p$$.

Since $$p-1=kn$$, we have \begin{aligned} x^{p-1}-1&=&(x^n-1)(x^{n(k-1)}+x^{n(k-2)}+...+x^n+1) \\&=&(x^n-1)f(x)\end{aligned} By Fermat’s little theorem, we know that $$x^{p-1}-1$$ has $$p-1$$ incongruent roots modulo $$p$$. Also, roots of $$x^{p-1}-1$$ are roots of $$f(x)$$ or a root of $$x^n-1$$. Notice that by Lagrange’s Theorem, we have that $$f(x)$$ has at most $$p-n-1$$ roots modulo $$p$$. Thus $$x^n-1$$ has at least $$n$$ roots modulo $$p$$. But again by Lagrange’s Theorem, since we have that $$x^n-1$$ has at most $$n$$ roots, thus we get that $$x^n-1$$ 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 $$p-1=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 $$p-1$$,

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^m-1$$ 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^m-1$$ 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 $$p-1=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 $$p-1$$, it follows that $p-1=\sum_{m\mid p-1}F(m).$ By Theorem 42, we see that $p-1=\sum_{m\mid p-1}\phi(m).$ By Lemma 1, $$F(m)\leq \phi(m)$$ when $$m\mid (p-1)$$. Together with $\sum_{m\mid p-1}F(m)=\sum_{m\mid p-1}\phi(m)$ we see that $$F(m)=\phi(m)$$ for each positive divisor $$m$$ of $$p-1$$. Thus we conclude that $$F(m)=\phi(m)$$. As a result, we see that there are $$p-1$$ incongruent integers of order $$p-1$$ modulo $$p$$. Thus $$p$$ has $$\phi(p-1)$$ primitive roots.

Exercises

1. Find the incongruent roots modulo 11 of $$x^2+2$$.

2. Find the incongruent roots modulo 11 of $$x^4+x^2+1$$.

3. Find the incongruent roots modulo 13 of $$x^3+12$$.

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

5. Find a complete set of incongruent primitive roots of 13.

6. Find a complete set of incongruent primitive roots of 17.

7. Find a complete set of incongruent primitive roots of 19.

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

9. 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.