Skip to main content
Mathematics LibreTexts

1.24: Theorems of Wilson, Euler, and Fermat

  • Page ID
    83359
  • \( \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}}\)

    As the Chinese Remainder Theorem illustrated in the last chapter, some useful and interesting number theoretic results deal with congruences. In this chapter we present a few more well known theorems involving congruences.

    Wilson’s Theorem

    For example, suppose that you took all the nonzero integers modulo \(m\) and multiplied them together (modulo \(m\)). What would you get? Let’s examine a few cases:

    In \(\mathbb{Z}_2\), \([1]\) \(=\) \([1]\).
    In \(\mathbb{Z}_3\), \([1][2]\) \(=\) \([2]\).
    In \(\mathbb{Z}_4\), \([1][2][3]\) \(=\) \([2]\).
    In \(\mathbb{Z}_5\), \([1][2][3][4]\) \(=\) \([4]\).
    In \(\mathbb{Z}_6\), \([1][2][3][4][5]\) \(=\) \([0]\).
    In \(\mathbb{Z}_7\), \([1][2][3][4][5][6]\) \(=\) \([6]\).
    In \(\mathbb{Z}_8\), \([1][2][3][4][5][6][7]\) \(=\) \([0]\).
    In \(\mathbb{Z}_9\), \([1][2][3][4][5][6][7][8]\) \(=\) \([0]\).
    In \(\mathbb{Z}_{10}\), \([1][2][3][4][5][6][7][8][9]\) \(=\) \([0]\).
    In \(\mathbb{Z}_{11}\), \([1][2][3][4][5][6][7][8][9][10]\) \(=\) \([10]\).
    In \(\mathbb{Z}_{12}\), \([1][2][3][4][5][6][7][8][9][10][11]\) \(=\) \([0]\).
    In \(\mathbb{Z}_{13}\), \([1][2][3][4][5][6][7][8][9][10][11][12]\) \(=\) \([12]\).

    A pattern seems to be emerging. When \(m\) is composite, it seems that \[\label{eq: nonprime Wilson} [1][2][3] \cdots [m-1] = [0],\] except in the case \(m=4\). When \(m\) is prime, it looks like \[\label{eq: Wilson in Zm} [1][2][3]\cdots[m-1] = [m-1].\]

    Perhaps you can see why at least some of this is true; Exercise \(\PageIndex{1}\) asks you to justify the pattern in equation \(\eqref{eq: nonprime Wilson}\). The equation \(\eqref{eq: Wilson in Zm}\) is known as Wilson’s Theorem,\(^{1}\) and we present it here in an equivalent form.

    Theorem \(\PageIndex{1}\): Wilson's Theorem

    If \(p\) is a prime, then \[(p-1)! \equiv -1 \pmod p.\nonumber \]

    Proof

    We present a sketch of the proof, which will rely on a few statements that are true but will not be proved here.

    Starting out, recall that \((p-1)! = 1\cdot 2 \cdot 3 \cdots \cdot (p-1)\), and the residue class modulo \(p\) to which this number belongs is the same class that \([1][2]\dots[p-1]\) equals.

    Suppose that \(p\) is prime; then the set \(\{[1],[2],\dots,[p-1]\}\) of nonzero elements in \(\mathbb{Z}_p\) is exactly the set of elements in \(U_p\). By Theorem 1.22.3 (4), each element in \(U_p\) has an inverse. A basic result in the theory of groups is that in every group, including \(U_p\), no two distinct elements have the same inverse, and if one group element is the inverse of another, then the latter element is the inverse of the former as well. This means that some of the elements in the product \([1][2]\cdots[p-1]\) can be collected into pairs of elements that are inverses of each other. These pairs will each “cancel,” leaving \([1]\) in their place (which we may ignore in the product, since they don’t affect that outcome, by Theorem 1.22.3 (3)). What is left in the product? The only terms of \([1][2]\cdots[p-1]\) that have not been canceled in this way are those that do not belong to an inverse pair; by Theorem 1.22.3(4) the only way this can happen is when an element is its own inverse. Which elements in \(U_p\) are their own inverses? Clearly \([1]\) and \([p-1]\) are their own inverses, so they remain when \([1][2]\cdots[p-1]\) is simplified. However, any element that is its own inverse satisfies \([x]^2 = [1]\), which is equivalent to the statement \(p \mid (x^2-1)=(x+1)(x-1)\). By Euclid’s Lemma (Lemma 1.11.2) this implies that \(p \mid (x+1)\) or \(p \mid (x-1)\), which means \(x \equiv -1 \pmod p\) or \(x \equiv 1 \pmod p\). Hence there are no other solutions to \([x]^2=[1]\) besides \([1]\) and \([p-1]\). Hence only \([1]\) and \([p-1]\) are their own inverses, and \[[1][2]\cdots[p-1] = [1][p-1] = [p-1].\nonumber \] Since \(-1 \in [p-1]\), our proof is complete.

    Let’s use an example to illustrate the proof of Wilson’s Theorem. Suppose that \(p=11\), and consider the product \[10! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10\nonumber \] modulo 11. In \(U_{11}\), we find the pairs of inverse elements, illustrated by

    \([1][1] = [1]\), \([2][6] = [1]\), \([3][4]=[1]\),
    [6pt] \([5][9]=[1]\), \([7][8] = [1]\), \([10][10] = [1]\).

    Now \[\begin{aligned} 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10 &\equiv 1 \cdot (2 \cdot 6) \cdot (3 \cdot 4) \cdot (5 \cdot 9) \cdot (7 \cdot 8) \cdot 10 \pmod{11}\\ &\equiv 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot 10 \pmod{11}\\ &\equiv 10 \pmod {11}\\ &\equiv -1 \pmod {11}.\end{aligned}\]

    Fermat’s Little Theorem and Euler’s Theorem

    We start this section by introducing Fermat’s Little Theorem.\(^{2}\) This theorem has far reaching consequences for applications to cryptography and secure transmission of data on the Internet.

    Theorem \(\PageIndex{2}\): Fermat's Little Theorem

    If \(p\) is prime and \(a\) is relatively prime to \(p\) then \[a^{p-1}\equiv 1 \pmod p.\nonumber \]

    Let’s look at some examples.

    Example \(\PageIndex{1}\)

    When \(p=2\), Fermat’s Little Theorem says that for any integer \(a\) relatively prime to 2 is congruent to 1 modulo 2; in other words, \(a\) is odd (hardly surprising!).

    When \(p=3\), the Theorem says that if \(a\) is not a multiple of 3, then \(a^2\) is one more than a multiple of three. We can verify this directly by noting that \[(3k+1)^2=9k^2+6k+1=3(3k^2+2k)+1\quad\text{and}\nonumber\] \[(3k+2)^2=9k^2+12k+4=3(3k^2+4k+1)+1\nonumber\] for all integers \(k\).

    When \(p=11\), Fermat’s Little Theorem says that any number \(a\) not divisible by 11 satisfies \(a^{10} \equiv 1 \pmod {11}\). For example, \[\begin{aligned} 2^{10} &= 1024 = 11\cdot 93 + 1;\\ 6^{10} &= 60466176 = 11\cdot 5496925 + 1; \text{ and of course}\\ 10^{10} &= 10000000000 = 9999999999+1 = 11\cdot 909090909 + 1.\end{aligned}\]

    From records available to us, it seems that Fermat’s Little Theorem was originally stated (without proof) in a letter Fermat wrote in 1640. A proof was presented by Euler in 1736, and later Euler published a theorem that holds not only for primes but for all positive integer moduli:\(^{3}\)

    Theorem \(\PageIndex{3}\): Euler's Theorem

    If \(m>0\) and \(a\) is relatively prime to \(m\) then \[a^{\phi(m)}\equiv 1\pmod m.\nonumber \]

    Example \(\PageIndex{2}\)

    Take \(m=12\); then \[\phi(m)=\phi\left(2^2\cdot3\right)=\left(2^2-2\right)(3-1)=4.\nonumber \] The positive integers \(a<m\) with \(\gcd(a,m)=1\) are \(1\), \(5\), \(7\) and \(11\). \[\begin{aligned} 1^4 &\equiv 1\pmod{12}\quad\text{is clear} \\ 5^2 &\equiv 1\pmod{12}\quad\text{since }12\mid (25-1) \\ \therefore\left(5^2\right)^2 &\equiv 1^2\pmod{12} \\ \therefore 5^4 &\equiv 1\pmod{12}. \end{aligned}\]

    Now \(7\equiv -5\pmod{12}\), and since \(4\) is even, \[\begin{aligned} 7^4 &\equiv (-5)^4 \equiv 5^4\pmod{12} \\ \therefore 7^4 &\equiv 1\pmod{12}. \end{aligned}\]

    Finally, \(11\equiv -1\pmod{12}\) and again, since \(4\) is even, we have \[11^4\equiv (-1)^4\pmod{12}\nonumber \] and \[11^4\equiv 1\pmod{12}.\nonumber \] This completes the verification of Euler’s Theorem for the case \(m=12\).

    Exercise \(\PageIndex{7}\) at the end of the chapter asks you to explain why Fermat’s Little Theorem can be derived as a consequence of Euler’s Theorem. Let’s now work towards proving Euler’s Theorem.

    Definition \(\PageIndex{1}\): Powers of Residue Classes

    If \([a]\in U_m\) define \([a]^1=[a]\) and for \(n>1\), \([a]^n=[a][a]\dotsm[a]\) where there are \(n\) copies of \([a]\) on the right.

    Theorem \(\PageIndex{4}\)

    If \([a]\in U_m\), then \([a]^n\in U_m\) for \(n\ge 1\) and \([a]^n=[a^n]\).

    Proof

    We prove that \([a]^n=[a^n]\in U_m\) for \(n\ge 1\) by induction on \(n\).

    If \(n=1\), \([a]^1=[a]=\left[a^1\right]\) and by assumption \([a]\in U_m\). Suppose \[[a]^k=\left[a^k\right]\in U_m\nonumber \] for some \(k\ge 1\). Then \[\begin{split} [a]^{k+1} &=[a]^k[a] \\ &=\left[a^k\right][a]\quad\text{by the induction hypothesis} \\ &=\left[a^ka\right]\quad\text{by Definition 21.1.4} \\ &=\left[a^{k+1}\right]\quad\text{since }a^ka=a^{k+1}. \end{split}\] So by the PMI, the theorem holds for \(n\ge 1\).

    Note that for fixed \(m>0\) if \(\gcd(a,m)=1\) then \([a]\in U_m\). And using Theorem \(\PageIndex{4}\) we have \[a^n\equiv 1\pmod m \quad \Longleftrightarrow \quad \left[a^n\right]=[1] \quad \Longleftrightarrow \quad [a]^n=[1].\nonumber \]

    It follows that Euler’s Theorem (Theorem \(\PageIndex{3}\)) is equivalent to the following theorem.

    Theorem \(\PageIndex{5}\)

    If \(m>0\) and \([a]\in U_m\) then \[[a]^{\phi(m)}=[1].\nonumber \]

    A proof of Theorem \(\PageIndex{5}\) is outlined in the Exercise \(\PageIndex{6}\) at the end of the chapter.

    Also Theorem \(\PageIndex{5}\) is an easy consequence of Lagrange’s Theorem, which students who take (or have taken) a course in abstract algebra will learn about (or will already know).

    To end this chapter, we note that Fermat’s Little Theorem can be used to simplify the computation of \(a^n\bmod p\) in the special case that \(p\) is prime. Recall that if \(a^n\equiv r\pmod p\) where \(0\le r<p\), then \(a^n\bmod p=r\). We can do two things to simplify the computation:

    1. Replace \(a\) by \(a\bmod p\).
    2. Replace \(n\) by \(n\bmod(p-1)\).

    We illustrate the technique with an example.

    Example \(\PageIndex{3}\)

    Suppose we want to calculate \[\label{comp_mod_11} 1234^{7865435}\bmod{11}.\nonumber \] We first replace \(1234\) by \(1234 \bmod{11}\). Since the modulus is 11, our job is made easier by Theorem 1.18.1 (e), and we can write \(1234\equiv (4 - 3 + 2 - 1)\pmod{11}\), that is, \(1234\equiv 2\pmod{11}\). Since \(\gcd(2,11)=1\) we have \(2^{10}\equiv1\pmod{11}\). Now \(7865435=(786543)\cdot 10+5\) so \[\begin{split} 2^{7865435} &\equiv 2^{(786543)\cdot10+5}\pmod{11} \\ &\equiv\left(2^{10}\right)^{786543}\cdot 2^5\pmod{11} \\ &\equiv 1^{786543}\cdot 2^5\pmod{11} \\ &\equiv 2^5\pmod{11}, \end{split}\] and \(2^5=32\equiv10\pmod{11}\). Hence, \[1234^{7865435}\equiv10\pmod{11}.\nonumber \] It follows that \[1234^{7865435}\bmod 11=10.\nonumber \]

    Exercises

    Exercise \(\PageIndex{1}\)

    Explain why when \(m\) is composite and not equal to 4, the equation \(\eqref{eq: nonprime Wilson}\) holds, i.e., \[[1][2][3] \cdots [m-1] = [0]\nonumber \] in \(\mathbb{Z}_m\).

    (Hint: handle the case where \(m\) is of the form \(p^2\), where \(p\) is prime, separately. When you handle this case, think about why \(m=4\) is an exception in the statement above.)

    Exercise \(\PageIndex{2}\)

    Let \(p\) be a prime.

    1. Use Wilson’s Theorem to show that if \(p \equiv 3 \pmod 4\), then \[\left[\left(\frac{p-1}{2}\right)!\right]^2 \equiv 1 \pmod p.\nonumber \] (Hint: show that the expression on the left is congruent to \(-(p-1)!\) modulo \(p\).)
    2. Show that if \(p \equiv 1 \pmod 4\), then \[\left[\left(\frac{p-1}{2}\right)!\right]^2 \equiv -1 \pmod p.\nonumber \]
    Exercise \(\PageIndex{3}\)

    Let \(p\) be a prime such that \(p \equiv 3 \pmod 4\).

    1. Show that \[(p-1)! \equiv -(1\cdot 3 \cdot 5 \cdots (p-2))^2 \pmod p.\nonumber \] (Hint: replace all the even multiplicands in \((p-1)!\) by congruent negative numbers.)
    2. Show that \[(1 \cdot 3 \cdot 5 \cdot \cdots \cdot (p-2))^2 \equiv 1 \pmod p.\nonumber \]
    3. Explain why \[1 \cdot 3 \cdot 5 \cdot \cdots \cdot (p-2) \equiv \pm 1 \pmod p.\nonumber \] (Use an idea from the proof of Wilson’s Theorem, or the result of Exercise 1.21.11.)
    4. Prove that if \(p \equiv 3 \pmod 4\), then \[2 \cdot 4 \cdot 6 \cdot \cdots \cdot (p-1) \equiv \mp 1 \pmod p.\nonumber \]
    Exercise \(\PageIndex{4}\)

    Let \(f\) be the function defined on the positive integers by \[f(n) = \left \lfloor \frac{n! \bmod (n+1)}{n}\right\rfloor(n-1)+2.\nonumber \]

    1. Compute \(f(1),f(2),\dots,f(10)\) and record the values.
    2. Explain why \(f(n)\) is always a prime number, no matter what positive integer \(n\) is.
    3. What do you think? How good is this function as a means for generating prime numbers?
    Exercise \(\PageIndex{5}\)

    Verify that Theorem \(\PageIndex{2}\) holds if \(p=5\) by direct calculation (as Theorem \(\PageIndex{3}\) was verified for \(m=12\) in Example \(\PageIndex{2}\)).

    Exercise \(\PageIndex{6}\)

    In this exercise you will prove Theorem \(\PageIndex{5}\). Let \(U_m = \{X_1, X_2, \dots, X_{\phi(m)} \}\). Here we write \(X_i\) for a residue class in \(U_m\) to simplify notation.

    1. Show that if \(X \in U_m\) then \[\{XX_1, XX_2, \cdots, XX_{\phi(m)} \} = U_m.\nonumber \]
    2. Explain why if \(X \in U_m\) then \[(XX_1)(XX_2)\cdots(XX_{\phi(m)}) = X_1X_2 \cdots X_{\phi(m)}.\nonumber \]
    3. Let \(A = X_1X_2 \cdots X_{\phi(m)}\). Show that if \(X \in U_m\) then \(X^{\phi(m)}A = A.\)
    4. Conclude from the last step that \(X^{\phi(m)} = [1]\) and hence Theorem \(\PageIndex{5}\) is true.
    Exercise \(\PageIndex{7}\)

    Show that Fermat’s Little Theorem follows quickly from Euler’s Theorem.

    Exercise \(\PageIndex{8}\)

    Show that if \(p\) is prime then \(a^p \equiv a \pmod p\) for all integers \(a\).

    (Hint: Consider two cases: (i) \(\gcd(a,p) = 1\) and (ii) \(\gcd(a,p) > 1\). Note that in the second case \(p \mid a\).)

    Exercise \(\PageIndex{9}\)

    Let \(m>0\). Let \(\gcd(a,m)=1\). Show that \(a^{\phi(m)-1}\) is an inverse for \(a\) modulo \(m\). (See Theorem 1.20.1.)

    Exercise \(\PageIndex{10}\)

    For all \(a\in\{1,2,3,4,5,6\}\) find an inverse \(a^\ast\) of \(a\) modulo \(7\) by using Exercise \(\PageIndex{9}\). Choose \(a^\ast\) in each case so that \(1\le a^\ast \le 6\).

    Exercise \(\PageIndex{11}\)
    1. Use the technique in Example \(\PageIndex{3}\) to calculate \[28^{1202}\bmod 13\nonumber \] (Since the modulus is not 11, you cannot use the same mod 11 trick (Theorem 1.18.1 (e)), of course.)
    2. Can you use Euler’s Theorem and reasoning similar to that of Example \(\PageIndex{3}\) to simplify \[29^{1202}\bmod 12?\nonumber \] If so, compute the answer; if not, explain why not.
    Exercise \(\PageIndex{12}\)

    Wilson’s Theorem implies that for every prime \(p\), the number \((p-1)!+1\) is divisible by \(p\). We call \(p\) a Wilson prime if even more is true—if the number \((p-1)!+1\) is divisible by \(p^2\). Find the smallest two Wilson primes (each is less than 20), and write a few sentences reporting on what is known and not currently known about Wilson primes, based on what you find through some research online.

    Footnotes

    [1] After John Wilson (1741{1793), though historians have identified work of the Arab mathematician and scientist Abu Ali al-Hasan ibn al-Haytham (also known as Alhazen, 965-1040) that shows he was aware of and made use of this fact. [7]

    [2] Fermat's Little Theorem is not the only theorem named after Fermat. His "big" theorem, or, as it is better known, Fermat's Last Theorem, states that \(x^n + y^n = z^n\) has no solutions in positive integers \(x,\: y,\: z\) when \(n > 2\). This was proved by Andrew Wiles in 1995 over 350 years after it was first mentioned by Fermat. It's an interesting story that has been the subject of books and a PBS special (Nova, "The Proof"), and you are encouraged to learn more about it.

    [3] Note the appearance here of Euler's totient function \(\phi\).


    This page titled 1.24: Theorems of Wilson, Euler, and Fermat is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Barrus & W. Edwin Clark.