3.3: Multiplicative Order and Applications

$\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}}$

In this section we prove two very useful results called Euler’s Theorem and Fermat’s Little Theorem (a special case of Euler’s). We do not follow the proof strategy of Euler and Fermat, however, instead using an approach inspired by abstract algebra and Lagrange’s Theorem in that subject.

First we need the

Definition: Multiplicative Order

Suppose $n\in\NN$ and $a\in\ZZ$ satisfy $n\ge2$ and $\gcd(a,n)=1$. Then we define the multiplicative order of $a$ in mod $n$ (called just the order when the multiplicative and $n$ can be understood from context) to be the smallest $k\in\NN$ such that $a^k\equiv1\pmod{n}$. The order of $a$ in mod $n$ is written $\ord_n(a)$.

Let us verify something which should probably always be checked for a new definition:

Proposition $\PageIndex{1}$

Given relatively prime numbers $n\in\NN$ and $a\in\ZZ$ with $n\ge2$, $\ord_n(a)$ is well-defined.

Proof

The problem in the definition of $\ord_n(a)$ might be that there might not be any value of $k\in\NN$ at all for which $a^k\equiv1\pmod{n}$.

But notice that this is a congruence, so we are really only concerned with the elements $a^k$ up to their congruence class.

So look at $\{[a^p]_n\mid p\in\NN\}$ and imagine putting the natural numbers $p\in\NN$ into different boxes based on what is the corresponding congruence class $[a^p]\in\ZZ/n\ZZ$. Since there are infinitely many elements in $\NN$ and only $n$ elements in $\ZZ/n\ZZ$ – $n$ boxes – by the Pigeonhole Principle (Theorem 1.1.1) there must be two (actually, infinitely many pairs of) distinct values $p,q\in\NN$ such that $p$ and $q$ end up in the same box, meaning $[a^p]=[a^q]$. Assume without loss of generality that $p>q$, so $p-q\in\NN$.

We are given that $\gcd(a,n)=1$, so by Corollary 2.2.1, $a^{-1}$ exists in mod $n$. Thus $$a^{p-q}\equiv a^p\,(a^{-1})^q\equiv a^q\,(a^{-1})^q\equiv a^0\equiv1\pmod{n}$$ (replacing $a^p$ with $a^q$ in the middle of this congruence since we know that $[a^p]=[a^q]$, which means $a^p\equiv a^q\pmod{n}$) and therefore the set of $k\in\NN$ for which $a^k\equiv1\pmod{n}$ is non-empty. The order is the smallest such value, which exists by the Well-Ordering Principle.

Here now is a theorem from abstract algebra (Lagrange’s Theorem) translated into the current context:

Theorem $\PageIndex{1}$

Given relatively prime numbers $n\in\NN$ and $a\in\ZZ$, $\ord_n(a)\mid\phi(n)$.

Proof

Start by looking at the congruence classes $[a],[a^2],[a^3]\dots$. They go up to $[a^{\ord_n(a)}]=[1]$ and then start to repeat, so the set $$\left<a\right>=\{[a^j]\mid j\in\NN, j\le\ord_n(a)\}$$ is a set of $\ord_n(a)$ elements of $\ZZ/n\ZZ$ (in group theory, this set $\left<a\right>$ is called the cyclic subgroup of $(\ZZ/n\ZZ)^*$ generated by $a$). Notice that because $a^{\ord_n(a)}\equiv1\pmod{n}$, $[1]\in\left<a\right>$. Also, since if $a^{-1}$ is the inverse of $a$ mod $n$, $(a^{-1})^k$ is the inverse of $a^k$ for $k\in\NN$, we see that $\left<a\right>\subseteq(\ZZ/n\ZZ)^*$.

To finish, we shall show that $(\ZZ/n\ZZ)^*$ is made up of some number, say $m$, of pieces, which we shall call cosets, each of which is bijective with $\left<a\right>$. These pieces will thus all have $\ord_n(a)$ elements, so $m\cdot\ord_n(a)=\#\left((\ZZ/n\ZZ)^*\right)=\phi(n)$, from which our desired result follows.

A coset of $\left<a\right>$ is a set of the form $$x\left<a\right>=\{[x]\cdot[a^j]=[x\,a^j]\mid j\in\NN, j\le\ord_n(a)\}$$ where $[x]\in(\ZZ/n\ZZ)^*$. We have observed that $[1]\in\left<a\right>$, so $\forall [x]\in(\ZZ/n\ZZ)^*$, $[x]\in x\left<a\right>$, meaning that every congruence class $[x]\in(\ZZ/n\ZZ)^*$ is in some coset, i.e., $$\ZZ/n\ZZ\subseteq\bigcup_{[x]\in(\ZZ/n\ZZ)^*}x\left<a\right>\ .$$

In fact, each coset $x\left<a\right>$ is bijective with $\left<a\right>$. The bijection is the map $f_x:\left<a\right>\to x\left<a\right>$ defined by $f_x([a^j])=[x a^j]$ for $j\in\NN$ with $j\le\ord_n(a)$. This map is a bijection because it has an inverse $f_{x^{-1}}$, coming from the inverse mod $n$ of $x$.

Now suppose $x\left<a\right>$ and $y\left<a\right>$ are two cosets. I claim that either $x\left<a\right>=y\left<a\right>$ or $x\left<a\right>\bigcap y\left<a\right>=\emptyset$. For this, suppose $x\left<a\right>\bigcap y\left<a\right>\neq\emptyset$, so $\exists [z]\in x\left<a\right>\bigcap y\left<a\right>$. That means that $\exists j,k\in\NN$ such that $j\le\ord_n(a)$, $k\le\ord_n(a)$, and $[xa^j]=[z]=[ya^k]$. In other words, $$xa^j\equiv ya^k\pmod{n}\ .$$ Without loss of generality, assume $j\le k$. Then if we multiply both sides of the above congruence by $(a^{-1})^j$, we have $x\equiv ya^{k-j}\pmod{n}$. But this means that every element $[x a^p]\in x\left<a\right>$ is can be expressed as $[y a^{p+k-j}]\in y\left<a\right>$, and every element $[y a^q]\in y\left<a\right>$ is can be expressed as $[x a^{q+j-k}]\in x\left<a\right>$. Thus $x\left<a\right>=y\left<a\right>$.

That was a lot of work, but now we get the famous theorems of Fermat’s Little and of Euler very easily.

Theorem $\PageIndex{2}$: Euler's Theorem

Say $a\in\ZZ$ and $n\in\NN$ satisfy $\gcd(a,n)=1$. Then $a^{\phi(n)}\equiv1\pmod{n}$.

Proof

The previous theorem, Theorem 3.3.1, told us that $\ord_n(a)\mid\phi(n)$, so $\exists m\in\ZZ$ such that $m\cdot\ord_n(a)=\phi(n)$. By the definition of order, this means $$a^{\phi(n)}\equiv a^{m\ord_n(a)}\equiv\left(a^{\ord_n(a)}\right)^m\equiv1^m\equiv1\pmod{n} .$$

Corollary $\PageIndex{1}$: Fermat's Little Theorem

If $p$ is a prime and $a\in\ZZ$ satisfies $\gcd(p,a)=1$ then $a^{p-1}\equiv1\pmod{p}$.

Proof

We have seen that for primes $p$, $\phi(p)=p-1$, so there is very little to do here.

Sometimes one sees Fermat’s Little Theorem in the following, different form:

Theorem $\PageIndex{3}$: Alternative Fermat's Little Theorem

If $p$ is a prime then $\forall a\in\ZZ$, $a^p\equiv a\pmod{p}$.

Proof

If $\gcd(a,p)=1$, then by Fermat’s Little, $a^{p-1}\equiv1\pmod{p}$. Multiplying both sides of this congruence by $a$ yields the desired result.

If instead $\gcd(a,p)\neq1$, it must be that $\gcd(a,p)=p$ since that gcd is a divisor of $p$, which is prime. The gcd is also a divisor of $a$, so in fact $p\mid a$. But then $a$ and all its powers are congruent mod $p$ to $0$, so $a^p\equiv0\equiv a\pmod{p}$.

Exercise $\PageIndex{1}$

1. What are the remainder when $15!$ is divided by $17$ and the remainder when $2\cdot(26!)$ is divided by $29$?
2. We know $17$ is prime (it’s just a wonderful number, isn’t it?). But just to be sure, use Wilson’s Theorem to prove it.
3. Can we build a test for primality out of Fermat’s Little Theorem? If so, would it be better (more efficient) than one based on Wilson’s Theorem? How would it work? Write a clear, formal statement of your proposed primality test.
4. If you know a programming language, write some code to try out your primality test. If not (or, in any case, after the programming), do a little research to see if this question has already been investigated and, if so, what was the conclusion. Give either a formal statement of the test and formal result describing its efficacy or a counter-example to your test that you found in the literature.
5. Suppose $p$ is an odd prime. Prove that if the quadratic congruence $x^2+1\equiv0\pmod{p}$ has a solution, then $p\equiv1\pmod{4}$. [Hint: Apply Fermat’s Little Theorem to a solution $a$ of the congruence, then multiply and divide by $2$ in the power.]