$$\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 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 5.1: The order of Integers and Primitive Roots

• • Contributed by Wissam Raji
• Associate Professor and the Chairman (Mathematics) at American University of Beirut

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

In this section, we study the order of an integer modulo $$n$$, where $$n$$ is positive. We also define primitive roots and related results. Euler’s theorem in Chapter 4 states that if a positive integer $$a$$ is relatively prime to $$n$$, then $$a^{\phi(n)}\equiv 1 (mod \ n)$$. Thus by the well ordering principle, there is a least positive integer $$x$$ that satisfies this congruence $$a^{x}\equiv 1 (mod \ n)$$.

Let $$(a,b)=1$$. The smallest positive integer $$x$$ such that $$a^{x} \equiv 1(mod \ b)$$ is called the order of $$a$$ modulo $$b$$. We denote the order of $$a$$ modulo $$b$$ by $$ord_ba$$.

$$ord_72=3$$ since $$2^3\equiv 1(mod \ 7)$$ while $$2^1\equiv 2(mod \ 7)$$ and $$2^2\equiv 4(mod \ 7)$$.

To find all integers $$x$$ such that $$a^x\equiv 1(mod \ b)$$, we need the following theorem.

If $$(a,b)=1$$ with $$b>0$$, then the positive integer $$x$$ is a solution of the congruence $$a^x\equiv 1(mod \ b)$$ if and only if $$ord_ba\mid x$$.

Having $$ord_ba\mid x$$, then we have that $$x=k.ord_ba$$ for some positive integer $$k$$. Thus $a^x=a^{kord_ba}=(a^{ord_ba})^k\equiv 1(mod \ b).$ Now if $$a^x\equiv 1(mod \ b)$$, we use the division algorithm to write $x=q ord_ba+r, \ \ \ 0\leq r<ord_ba.$ Thus we see that $a^x\equiv a^{qord_ba+r}\equiv (a^{ord_ba})^qa^r\equiv a^r (mod \ b).$ Now since $$a^x\equiv 1(mod \ b)$$,we have $$a^r\equiv 1(mod \ b)$$. Since $$ord_ba$$, we get $$r=0$$. Thus $$x=q.ord_ba$$ and hence $$ord_ba\mid x$$.

Since $$ord_72=3$$, then $$2^{15}\equiv 1(mod \ 7)$$ while 10 is not a solution for $$2^x\equiv 1 (mod \ 7)$$.

If $$(a,b)=1$$ with $$b>0$$, then $a^i\equiv a^j(mod \ b)$ where $$i$$ and $$j$$ are nonnegative integers, if and only if $i\equiv j(mod \ ord_ba)$

Suppose that $i\equiv j(mod \ ord_ba)\ \ \mbox{and}\ \ 0\leq j\leq i.$ Then we have $$i-j=k.ord_ba$$, where $$k$$ is a positive integer. Hence $a^i=a^{j+k.ord_ba}=a^j(a^{ord_ba})^k\equiv a^j (mod \ b).$ Assume now that $$a^i\equiv a^j(mod \ b)$$ with $$i\geq j$$. Thus we have $a^i\equiv a^ja^{i-j}\equiv a^j(mod \ b)$ Since $$(a,b)=1$$, we have $$(a^j,b)=1$$ and thus by Theorem 22, we get $a^{i-j}\equiv 1(mod \ b).$ By theorem 54, we get that $$ord_ba \mid (i-j)$$ and hence $$i\equiv j(mod \ b)$$.

We introduce now primitive roots and discuss their properties. We are interested in integers whose order modulo another integer is $$\phi(b)$$. In one of the exercises, one is asked to prove that if $$a$$and $$b$$ are relatively prime then $$ord_ba \mid \phi(b)$$.

If $$(r,m)=1$$ with $$m>0$$ and if $$ord_mr=\phi(m)$$ then $$r$$ is called a primitive root modulo $$m$$.

Notice that $$\phi(7)=6$$ hence $$2$$ is not a primitive root modulo $$7$$. While $$ord_73=6$$ and thus $$3$$ is a primitive root modulo $$7$$.

If $$(r,m)=1$$ with $$m>0$$ and if $$r$$ is a primitive root modulo $$n$$, then the integers $$\{r^1,r^2,...r^{\phi(m)}\}$$ form a reduced residue set modulo $$m$$.

To prove that the set $$\{r^1,r^2,...r^{\phi(m)}\}$$ form a reduced residue set modulo $$m$$ we need to show that every two of them are relatively prime and that no two of them are congruent modulo $$m$$. Since $$(r,m)=1$$, it follows that $$(r^n,m)=1$$ for all positive integers $$n$$. Hence all the powers of $$r$$ are relatively prime to $$m$$. To show that no two powers in the above set are equivalent modulo $$m$$, assume that $r^i\equiv r^j(mod \ m).$ By Theorem 55, we see that $i\equiv j(mod \ ord_m\phi(m)).$ Notice that $$1\leq i,j\leq \phi(m)$$ and hence $$i=j$$.

If $$ord_ma=t$$ and if $$u$$ is a positive integer, then $ord_m(a^u)=t/(t,u).$

Let $v=ord_m(a^u),\ \ w=(t,u), \ \ t=t_1w \mbox{and}\ \ u=u_1w.$ Notice that $$(t_1,u_1)=1.$$

Because $$t_1=t/(t,u)$$, we want to show that $$ord_m(a^u)=t_1$$. To do this, we will show that $$(a^{u})^{t_1}\equiv 1(mod \ m)$$ and that if $$(a^u)^v\equiv 1(mod \ m)$$, then $$t_1\mid v$$. First note that $(a^u)^{t_1}=(a^{u_1w})^{(t/w)}=(a^t)^{u_1}\equiv 1(mod \ m).$ Hence by Theorem 54, we have $$v\mid t_1$$. Now on the other hand, since $(a^u)^v=a^{uv}\equiv 1(mod \ m),$ we know that $$t\mid uv$$. Hence $$t_1w\mid u_1wv$$ and hence $$t_1\mid u_1v$$. Because $$(t_1,u_1)=1$$, we see that $$t_1\mid v$$. Since $$v\mid t_1$$ and $$t_1\mid v$$, we conclude that $$v=t_1=t/w=t/(t,u)$$.

We see that $$ord_73^4=6/(6,4)$$ since $$ord_73=6$$.

Let $$r$$ be a primitive root modulo $$m$$, where $$m$$ is a positive integer, $$m>1$$. Then $$r^u$$ is a primitive root modulo $$m$$ if and only if $$(u,\phi(m))=1$$.

By Theorem 57, we see that $ord_mr^u=ord_mr/(u,ord_mr)=\phi(m)/(u,\phi(m)).$ Thus $$ord_mr^u=\phi(m)$$ and $$r^u$$ is a primitive root if and only if $$(u,\phi(m))=1$$.

The above corollary leads to the following theorem

If the positive integer $$m$$ has a primitive root, then it has a total of $$\phi(\phi(m))$$ incongruent primitive roots.

Let $$r$$ be a primitive root modulo $$m$$. By Theorem 56, we see that $$\{r^1,r^2,...,r^{\phi(m)}\}$$ form a reduced residue system modulo $$n$$. By Corollary 1, it is known that $$r^u$$ is a primitive root modulo $$m$$ if and only if $$(u,\phi(m))=1$$. Thus we have exactly $$\phi(\phi(m))$$ such integers $$u$$ that are relatively prime to $$\phi(m)$$ and hence there are exactly $$\phi(\phi(m))$$ primitive roots modulo $$m$$.

Exercises

1. Determine $$ord_{13}10$$.

2. Determine $$ord_{11}3.$$

3. Show that 5 is a primitive root of 6.

4. Show that if $$\bar{a}$$ is an inverse of $$a$$ modulo $$n$$, then $$ord_na=ord_n\bar{a}$$.

5. Show that if $$n$$ is a positive integer, and $$a$$ and $$b$$ are integers relatively prime to $$n$$ such that $$(ord_na,ord_nb)=1$$, then $$ord_n(ab)=ord_na.ord_nb$$.

6. Show that if $$a$$ is an integer relatively prime to the positive integer $$m$$ and $$ord_ma=st$$, then $$ord_ma^t=s$$.

7. Show that if $$a$$ and $$n$$ are relatively prime with $$n>0$$, then $$ord_na \mid \phi(n)$$.

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