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

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\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]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\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]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

$$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$$

$$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$$

$$\newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vectorC}[1]{\textbf{#1}}$$

$$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$$

$$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$$

$$\newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}}$$

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

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

$$\newcommand{\avec}{\mathbf a}$$ $$\newcommand{\bvec}{\mathbf b}$$ $$\newcommand{\cvec}{\mathbf c}$$ $$\newcommand{\dvec}{\mathbf d}$$ $$\newcommand{\dtil}{\widetilde{\mathbf d}}$$ $$\newcommand{\evec}{\mathbf e}$$ $$\newcommand{\fvec}{\mathbf f}$$ $$\newcommand{\nvec}{\mathbf n}$$ $$\newcommand{\pvec}{\mathbf p}$$ $$\newcommand{\qvec}{\mathbf q}$$ $$\newcommand{\svec}{\mathbf s}$$ $$\newcommand{\tvec}{\mathbf t}$$ $$\newcommand{\uvec}{\mathbf u}$$ $$\newcommand{\vvec}{\mathbf v}$$ $$\newcommand{\wvec}{\mathbf w}$$ $$\newcommand{\xvec}{\mathbf x}$$ $$\newcommand{\yvec}{\mathbf y}$$ $$\newcommand{\zvec}{\mathbf z}$$ $$\newcommand{\rvec}{\mathbf r}$$ $$\newcommand{\mvec}{\mathbf m}$$ $$\newcommand{\zerovec}{\mathbf 0}$$ $$\newcommand{\onevec}{\mathbf 1}$$ $$\newcommand{\real}{\mathbb R}$$ $$\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$$ $$\newcommand{\laspan}[1]{\text{Span}\{#1\}}$$ $$\newcommand{\bcal}{\cal B}$$ $$\newcommand{\ccal}{\cal C}$$ $$\newcommand{\scal}{\cal S}$$ $$\newcommand{\wcal}{\cal W}$$ $$\newcommand{\ecal}{\cal E}$$ $$\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$$ $$\newcommand{\gray}[1]{\color{gray}{#1}}$$ $$\newcommand{\lgray}[1]{\color{lightgray}{#1}}$$ $$\newcommand{\rank}{\operatorname{rank}}$$ $$\newcommand{\row}{\text{Row}}$$ $$\newcommand{\col}{\text{Col}}$$ $$\renewcommand{\row}{\text{Row}}$$ $$\newcommand{\nul}{\text{Nul}}$$ $$\newcommand{\var}{\text{Var}}$$ $$\newcommand{\corr}{\text{corr}}$$ $$\newcommand{\len}[1]{\left|#1\right|}$$ $$\newcommand{\bbar}{\overline{\bvec}}$$ $$\newcommand{\bhat}{\widehat{\bvec}}$$ $$\newcommand{\bperp}{\bvec^\perp}$$ $$\newcommand{\xhat}{\widehat{\xvec}}$$ $$\newcommand{\vhat}{\widehat{\vvec}}$$ $$\newcommand{\uhat}{\widehat{\uvec}}$$ $$\newcommand{\what}{\widehat{\wvec}}$$ $$\newcommand{\Sighat}{\widehat{\Sigma}}$$ $$\newcommand{\lt}{<}$$ $$\newcommand{\gt}{>}$$ $$\newcommand{\amp}{&}$$ $$\definecolor{fillinmathshade}{gray}{0.9}$$

$$\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\{[0]_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}$$.

This page titled 3.4: Another Approach to Fermat's Little and Euler's Theorems is shared under a CC BY-SA license and was authored, remixed, and/or curated by Jonathan A. Poritz.