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.2: Wilson's Theorem

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

    In this section, we prove a nice theorem usually named after an \(18^{\text{th}}\) century English mathematician ... although it was actually first stated by Ibn al-Haytham nearly \(800\) years earlier.

    First, we need a Lemma.

    Lemma \(\PageIndex{1}\)

    Let \(p\) be a prime. Then \(n\in\NN\) equals its own inverse mod \(p\) if and only if \(p\mid n+1\) or \(p\mid n-1\), i.e., iff \(n\equiv\pm1\pmod{p}\).

    Proof

    Say \(p\) is a prime and \(n\in\NN\) equals its own inverse mod \(p\). That means that \(n^2=n\cdot n\equiv1\pmod{p}\). By definition, \(p\mid n^2-1=(n+1)(n-1)\). By Proposition 3.1.1, this means that either \(p\mid n+1\) or \(p\mid n-1\).

    For the converse, suppose \(n\equiv1\pmod{p}\) or \(n\equiv-1\pmod{p}\). Then, by Theorem 2.1.1, \(n^2\equiv(\pm 1)^2=1\pmod{p}\), so \(n\) equals its own inverse mod \(p\).

    This Lemma is a key step in

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

    Given \(p\in\NN\) such that \(p\ge2\), \(p\) is prime iff \((p-1)!\equiv-1\pmod{p}\).

    Proof

    Suppose \(p\) is prime. Consider the terms of \((p-2)!\): every one has an inverse mod \(p\) by Corollary 2.2.1, and only \(1\) equals its own inverse mod \(p\) (so would \(p-1\), but it is not in the product \((p-2)!\) by Lemma 3.2.1. Hence in \((p-1)!\) we can group the terms into pairs (\((p-3)/2\) of these pairs) which are inverses mod \(p\), leaving out only \(1\) and \((p-1)\). That is \[(p-1)! \equiv 1^{(p-3)/2}(p-1) \equiv p-1\equiv -1\pmod{p}\]

    Conversely, suppose \(p\in\NN\) satisfies \(p\ge2\) and \((p-1)!\equiv-1\pmod{p}\). We can rewrite that congruence as \((p-1)!+1\equiv0\pmod{p}\), or \(p\mid((p-1)!+1)\).

    Now let \(d\in\NN\) be a divisor of \(p\) such that \(d\neq p\). It follows that \(d\) is one of the numbers in the product \((p-1)!\), so \(d\mid(p-1)!\); also, since \(d\mid p\) and \(p\mid((p-1)!+1)\), it follows that \(d\mid((p-1)!+1)\). Therefore, \(d\mid((p-1)!+1)-(p-1)! = 1\) by Theorem 1.3.2, which means \(d=1\).

    In other words, if \(d\in\NN\) is a divisor of \(p\), it must be either \(p\) or \(1\), so \(p\) is prime.

    Example \(\PageIndex{1}\)

    Let’s work through one direction of the proof for a simple case, say of \(p=7\). We start by finding all the inverses of the numbers \(2,\dots,6\) (by brute force, in this small case): \(2\cdot4\equiv1\pmod{7}\) and \(3\cdot5\equiv1\pmod{7}\), meaning that \(2^{-1}\equiv4\) (or\(4^{-1}\equiv2\)) and \(3^{-1}\equiv5\) (or \(5^{-1}\equiv3\)).

    Then \[(p-2)! = 5! = 5\cdot4\cdot3\cdot2\cdot1=(5\cdot3)\cdot(4\cdot2)\equiv1\cdot1\equiv1\pmod{7}\] which in turn means that \[(p-1)! = 6! = 6\cdot5!\equiv6\cdot1\equiv6\equiv7-1\equiv-1\pmod{7}\ .\]

    Notice that Wilson’s Theorem can be used to build a test for primality: see if a number \(n\) satisfies \((n-1)!\equiv-1\pmod{n}\) and, if so, \(n\) is prime. This is an entirely impractical test, but it is our first example of a simple computational congruence involving an integer which can tell us that that integer is prime.

    • Was this article helpful?