Loading [MathJax]/extensions/TeX/mathchoice.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

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

( \newcommand{\kernel}{\mathrm{null}\,}\)













There is another way to think about these theorems which we shall explain here, because it usefully fills out our understanding of multiplication in Z/nZ. 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 3.4.1: Fermat's Little Theorem, Redux

If p is a prime and aZ 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.

  • Was this article helpful?

Support Center

How can we help?