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

\(\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}\).