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

# 3.4: Another Approach to Fermat's Little and Euler's Theorems

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\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}}$$ $$\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}}$$

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

There is another way to think about these theorems which we shall explain here, because it usefully fills out our understanding of multiplication in $$\ZZ/n\ZZ$$. In this case, we shall consider the theorems in the reverse order to what we used above – which is in fact more historically accurate.

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

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

Proof

Let’s start by proving that the set $M_a=\left\{_p,[a]_p,[2a]_p,\dots,[(p-1)a]_p\right\}$ of multiples of $$[a]_p$$ in $$\ZZ/p\ZZ$$ has $$p$$ elements.

There are only $$p$$ congruence classes named between the $$\{$$ and $$\}$$, so the set cannot have more than $$p$$ elements.

Now look at two elements in this set, call them $$[ja]_p$$ and $$[ka]_p$$ with $$0\le j,k<p$$, and suppose they are equal. That means that $$ja\equiv ka\pmod{p}$$, or $$p\mid (j-k)a$$. By Proposition 3.1.1, this means that either $$p\mid (j-k)$$ or $$p\mid a$$. Since $$\gcd(p,a)=1$$, we cannot have $$p\mid a$$. Thus $$p\mid (j-k)$$.

But $$0\le j,k<p$$ tells us that $$-p+1<j-k<p-1$$ and the only multiple of $$p$$ in this range is $$0$$. Therefore $$j=k$$, and this means that all of the elements in the above description of $$M_a$$ are distinct, so indeed $$\#(M_a)=p$$. But we already know that $$\ZZ/p\ZZ$$ itself has $$p$$ elements, which means $$M_a$$ above is simply another way of describing $$\ZZ/p\ZZ$$.

For our next step, let’s multiply together all the nonzero elements of $$M_a$$, or of $$\ZZ/p\ZZ$$ since we know it’s the same thing: $a\cdot2a\cdot\dots\cdot(p-1)a\equiv1\cdot\cdot2\cdot\dots\cdot(p-1)\pmod{p}\ .$ Rearranging these terms, we see $a^{p-1}(p-1)!\equiv(p-1)!\pmod{p}$ or $$p\mid(a^{p-1}-1)\,(p-1)!$$. Since $$p$$ being prime means $$\gcd(p,(p-1)!)=1$$, it follows by Proposition 3.1.1 that $$p\mid a^{p-1}-1$$. That is, $$a^{p-1}\equiv1\pmod{p}$$, as desired.

The above is quite similar to the proof that Euler gave of Fermat’s Little Theorem (actually, Fermat gave no proof at all – not unlike his famous Last “Theorem”). A very similar strategy can also prove his own theorem:

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

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

Proof

Recall that the set $$(\ZZ/n\ZZ)^*$$ of (multiplicatively) invertible elements in $$\ZZ/n\ZZ$$ can be written as $$\{[b_1]_n,\dots,[b_{\phi(n)}]_n\}$$ where the numbers $$b_1,\dots,b_{\phi(n)}$$, satisfying $$1\le b_1<\dots<b_{\phi(n)}<n$$, are all relatively prime to $$n$$.

We claim that we can also describe $$(\ZZ/n\ZZ)^*$$ as the set $M_a^*=\left\{[b_1a]_n,\dots,[b_{\phi(n)}]_n\right\}\ .$ Note first that since each $$b_j$$ is relatively prime to $$n$$, and so is $$a$$, it follows that $$b_ja$$ is relatively prime to $$n$$ as well – the primes which divide $$b_ja$$ divide either $$b_j$$ or $$a$$, and there are no such primes which also divide $$n$$. Therefore $$M_a^*\subseteq(\ZZ/n\ZZ)^*$$.

Now notice that if $$[b_ja]_n=[b_ka]_n$$ for $$1\le j,k\le\phi(n)$$ then $$n\mid(b_j-b_k)a$$. By Euclid’s Lemma 2.1.1 since $$\gcd(a,n)=1$$, we must have $$n\mid(b_j-b_k)$$.

However, since $$1\le b_1<\dots<b_{\phi(n)}<n$$, it follows that $$-n+1<b_j-b_k<n-1$$, and the only multiple of $$n$$ in that range is $$0$$. Thus $$b_j=b_k$$ and we conclude that all of the elements in the above description of $$M_a^*$$ are distinct. Since there are $$\phi(n)$$ such elements and $$M_a^*$$ is a subset of $$(\ZZ/n\ZZ)^*$$, which has only $$\phi(n)$$ elements, it must be that $$M_a^*=(\ZZ/n\ZZ)^*$$.

As in the previous proof, we conclude that the products of all the elements in $$M_a^*$$ and in $$(\ZZ/n\ZZ)^*$$ must be the same: $b_1a\cdot\dots\cdot b_{\phi(n)}a\equiv b_1\cdot\dots\cdot b_{\phi(n)}\pmod{n}\ .$ Regrouping terms again, we see $a^{\phi(n)}b_1\cdot\dots\cdot b_{\phi(n)}\equiv b_1\cdot\dots\cdot b_{\phi(n)}\pmod{n}\ .$ Now the $$b$$’s are all invertible mod $$n$$, so we can multiply by the inverses, one by one, until we are left with $a^{\phi(n)}\equiv1\pmod{n}$ which finishes Euler’s Theorem.

Exercise $$\PageIndex{1}$$

1. Let $$n$$, $$a$$, and $$b_1,\dots,b_{\phi(n)}$$ be as in the proof of Euler’s Theorem. Show that $$b_1\cdot\dots\cdot b_{\phi(n)}\equiv\pm1\pmod{n}$$.