Skip to main content
\(\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}}\)
Mathematics LibreTexts

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

  • Page ID
    28642
  • \( \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{\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}\).
    • Was this article helpful?