Editing Wilson's theorem

{{Short description|Theorem on prime numbers}}
{{CS1 config|mode=cs1}}
In [[algebra]] and [[number theory]], '''Wilson's theorem''' states that a [[natural number]] ''n'' > 1 is a [[prime number]] [[if and only if]] the product of all the [[positive integer]]s less than ''n'' is one less than a multiple of ''n''.  That is (using the notations of [[modular arithmetic]]), the [[factorial]] <math>(n - 1)! = 1 \times 2 \times 3 \times \cdots \times (n - 1)</math> satisfies

:<math>(n-1)!\ \equiv\; -1 \pmod n</math>

exactly when ''n'' is a prime number. In other words, any integer ''n'' > 1 is a prime number if, and only if, (''n''&thinsp;−&thinsp;1)!&nbsp;+&nbsp;1 is divisible by ''n''.<ref>''The Universal Book of Mathematics.'' David Darling, p. 350.</ref>

==History==
The theorem was first stated by [[Ibn al-Haytham]] {{circa|1000 AD}}.<ref>{{MacTutor Biography|id=Al-Haytham|title=Abu Ali al-Hasan ibn al-Haytham}}</ref> [[Edward Waring]] announced the theorem in 1770 without proving it, crediting his student [[John Wilson (mathematician and judge)|John Wilson]] for the discovery.<ref>Edward Waring, ''Meditationes Algebraicae'' (Cambridge, England:  1770), page 218 (in Latin).  In the third (1782) edition of Waring's ''Meditationes Algebraicae'', Wilson's theorem appears as problem 5 on [https://books.google.com/books?id=1MNbAAAAQAAJ&pg=PA380 page 380].  On that page, Waring states:  "Hanc maxime elegantem primorum numerorum proprietatem invenit vir clarissimus, rerumque mathematicarum peritissimus Joannes Wilson Armiger."  (A man most illustrious and most skilled in mathematics, Squire John Wilson, found this most elegant property of prime numbers.)</ref> [[Joseph Louis Lagrange|Lagrange]] gave the first proof in 1771.<ref>Joseph Louis Lagrange, [https://books.google.com/books?id=_-U_AAAAYAAJ&pg=PA125 "Demonstration d'un théorème nouveau concernant les nombres premiers"] (Proof of a new theorem concerning prime numbers), ''Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettres'' (Berlin), vol. 2, pages 125–137 (1771).</ref>  There is evidence that [[Gottfried Leibniz|Leibniz]] was also aware of the result a century earlier, but never published it.<ref>[[Giovanni Vacca (mathematician)|Giovanni Vacca]] (1899) "Sui manoscritti inediti di Leibniz" (On unpublished manuscripts of Leibniz),
''Bollettino di bibliografia e storia delle scienze matematiche'' ... (Bulletin of the bibliography and history of mathematics), vol. 2, pages 113–116; see [https://books.google.com/books?id=vqwSAQAAMAAJ&pg=PA114 page 114] (in Italian).  Vacca quotes from Leibniz's mathematical manuscripts kept at the Royal Public Library in Hanover (Germany), vol. 3 B, bundle 11, page 10:  <blockquote>''Original'' :  Inoltre egli intravide anche il teorema di Wilson, come risulta dall'enunciato seguente:<br/>"Productus continuorum usque ad numerum qui antepraecedit datum divisus per datum relinquit 1 (vel complementum ad unum?) si datus sit primitivus.  Si datus sit derivativus relinquet numerum qui cum dato habeat communem mensuram unitate majorem."<br/>Egli non giunse pero a dimostrarlo.</blockquote><blockquote>''Translation'' :  In addition, he [Leibniz] also glimpsed Wilson's theorem, as shown in the following statement:<br/>"The product of all integers preceding the given integer, when divided by the given integer, leaves 1 (or the complement of 1?) if the given integer be prime.  If the given integer be composite, it leaves a number which has a common factor with the given integer [which is] greater than one."<br/>However, he didn't succeed in proving it.</blockquote> See also:  Giuseppe Peano, ed., ''Formulaire de mathématiques'', vol. 2, no. 3, [https://archive.org/details/formulairedemat02peangoog/page/n231 page 85] (1897).</ref>

==Example==
For each of the values of ''n'' from 2 to 30, the following table shows the number (''n''&thinsp;−&thinsp;1)! and the remainder when (''n''&thinsp;−&thinsp;1)! is divided by ''n''.  (In the notation of [[modular arithmetic]], the remainder when ''m'' is divided by ''n'' is written ''m'' mod ''n''.)
The background color is blue for <span style="background-color:#94DCF2">prime</span> values of ''n'', gold for <span style="background-color:#E6C647">composite</span> values.
{| class="wikitable" style="text-align:right"
|+ Table of factorial and its remainder modulo ''n''
! <math>n</math> !! <math>(n-1)!</math> <br/> {{OEIS|id=A000142}} !! <math>(n-1)!\ \bmod\ n</math> <br/> {{OEIS|id=A061006}}
|- style="background-color:#94DCF2"
| 2 || 1 || 1
|- style="background-color:#94DCF2"
| 3 || 2 || 2
|- style="background-color:#E6C647"
| 4 || 6 || 2
|- style="background-color:#94DCF2"
| 5 || 24 || 4
|- style="background-color:#E6C647"
| 6 || 120 || 0
|- style="background-color:#94DCF2"
| 7 || 720 || 6
|- style="background-color:#E6C647"
| 8 || 5040 || 0
|- style="background-color:#E6C647"
| 9 || 40320 || 0
|- style="background-color:#E6C647"
| 10 || 362880 || 0
|- style="background-color:#94DCF2"
| 11 || 3628800 || 10
|- style="background-color:#E6C647"
| 12 || 39916800 || 0
|- style="background-color:#94DCF2"
| 13 || 479001600 || 12
|- style="background-color:#E6C647"
| 14 || 6227020800 || 0
|- style="background-color:#E6C647"
| 15 || 87178291200 || 0
|- style="background-color:#E6C647"
| 16 || 1307674368000 || 0
|- style="background-color:#94DCF2"
| 17 || 20922789888000 || 16
|- style="background-color:#E6C647"
| 18 || 355687428096000 || 0
|- style="background-color:#94DCF2"
| 19 || 6402373705728000 || 18
|- style="background-color:#E6C647"
| 20 || 121645100408832000 || 0
|- style="background-color:#E6C647"
| 21 || 2432902008176640000 || 0
|- style="background-color:#E6C647"
| 22 || 51090942171709440000 || 0
|- style="background-color:#94DCF2"
| 23 || 1124000727777607680000 || 22
|- style="background-color:#E6C647"
| 24 || 25852016738884976640000 || 0
|- style="background-color:#E6C647"
| 25 || 620448401733239439360000 || 0
|- style="background-color:#E6C647"
| 26 || 15511210043330985984000000 || 0
|- style="background-color:#E6C647"
| 27 || 403291461126605635584000000 || 0
|- style="background-color:#E6C647"
| 28 || 10888869450418352160768000000 || 0
|- style="background-color:#94DCF2"
| 29 || 304888344611713860501504000000 || 28
|- style="background-color:#E6C647"
| 30 || 8841761993739701954543616000000 || 0
|}

==Proofs==
As a [[biconditional]] (if and only if) statement, the proof has two halves: to show that equality ''does not'' hold when <math>n</math> is composite, and to show that it ''does'' hold when <math>n</math> is prime.

===Composite modulus===
Suppose that <math>n</math> is composite.  Therefore, it is divisible by some prime number <math>q</math> where <math>2 \leq q < n</math>. Because <math>q</math> divides <math>n</math>, there is an integer <math>k</math> such that <math>n = qk</math>. Suppose for the sake of contradiction that <math>(n-1)! </math> were congruent to <math>-1</math> modulo <math>{n}</math>. Then <math>(n-1)!</math> would also be congruent to <math>-1</math> modulo <math>{q}</math>: indeed, if <math>(n-1)! \equiv -1 \pmod{n}</math> then <math>(n-1)! = nm - 1 = (qk)m - 1 = q(km) - 1</math> for some integer <math>m</math>, and consequently <math>(n-1)!</math> is one less than a multiple of <math>q</math>.  On the other hand, since <math>2 \leq q \leq n - 1</math>, one of the factors in the expanded product <math>(n - 1)! = (n - 1) \times (n - 2) \times \cdots \times 2 \times 1</math> is <math>q</math>.  Therefore <math>(n - 1)! \equiv 0 \pmod{q}</math>.  This is a contradiction; therefore it is not possible that <math>(n - 1)! \equiv -1\pmod{n}</math> when <math>n</math> is composite.

In fact, more is true. With the sole exception of the case <math>n = 4</math>, where <math>3! = 6 \equiv 2 \pmod{4}</math>, if <math>n</math> is composite then <math>(n - 1)!</math> is congruent to 0 modulo <math>n</math>. The proof can be divided into two cases: First, if <math>n</math> can be factored as the product of two unequal numbers, <math>n = ab</math>, where <math>2 \leq a < b < n</math>, then both <math>a</math> and <math>b</math> will appear as factors in the product <math>(n - 1)! = (n - 1)\times (n - 2) \times \cdots \times 2 \times 1</math> and so <math>(n - 1)!</math> is divisible by <math>ab = n</math>.  If <math>n</math> has no such factorization, then it must be the square of some prime <math>q</math> larger than 2. But then <math>2q < q^2 = n</math>, so both <math>q</math> and <math>2q</math> will be factors of <math>(n-1)!</math>, and so <math>n</math> divides <math>(n-1)!</math> in this case, as well.

===Prime modulus===

The first two proofs below use the fact that the [[residue class]]es modulo a prime number form a [[finite field]] (specifically, a [[prime field]]).<ref>{{cite book|last=Landau|first=Edmund|orig-date=1927|date=1966|title=Elementary Number Theory|edition=2nd|chapter=Part One, Chapter V: Congruences, Theorem 77|url=https://archive.org/details/elementarynumber0000edmu_u9d2/page/50|location=New York|publisher=Chelsea Publishing Company|pages=51-52|lccn=66002147|oclc=1420155|ol=5976039M|access-date=2025-02-06}}</ref>

====Elementary proof====

The result is trivial when <math>p = 2</math>, so assume <math>p</math> is an odd prime, <math>p \geq 3</math>. Since the residue classes modulo <math>p</math> form a field, every non-zero residue <math>a</math> has a unique multiplicative inverse <math>a^{-1}</math>. [[Euclid's lemma]] implies{{efn|Because if <math>a \equiv a^{-1} \pmod{p}</math> then <math>a^2 -1 \equiv 0 \pmod{p}</math>, and if the prime <math>p</math> divides <math>a^2 - 1 = (a - 1)(a + 1)</math>, then by [[Euclid's lemma]] it divides either <math>a - 1</math> or <math>a + 1</math>.}} that the only values of <math>a</math> for which <math>a \equiv a^{-1}\pmod{p}</math> are <math>a \equiv \pm 1 \pmod{p}</math>.  Therefore, with the exception of <math>\pm 1</math>, the factors in the expanded form of <math>(p - 1)!</math> can be arranged in disjoint pairs such that product of each pair is congruent to 1 modulo <math>p</math>. This proves Wilson's theorem.

For example, for <math>p = 11</math>, one has
<math display="block">10! = [(1\cdot10)]\cdot[(2\cdot6)(3\cdot4)(5\cdot9)(7\cdot8)]  \equiv [-1]\cdot[1\cdot1\cdot1\cdot1]  \equiv -1 \pmod{11}.</math>

====Proof using Fermat's little theorem====

Again, the result is trivial for ''p''&nbsp;=&nbsp;2, so suppose ''p'' is an odd prime, {{nowrap|1=''p'' ≥  3}}. Consider the polynomial

:<math>g(x)=(x-1)(x-2) \cdots (x-(p-1)).</math>

''g'' has degree {{nowrap|1=''p'' − 1}}, leading term {{nowrap|1=''x''<sup>''p'' − 1</sup>}}, and constant term {{nowrap|1=(''p'' − 1)!}}. Its {{nowrap|1=''p'' − 1}} roots are 1, 2, ..., {{nowrap|1=''p'' − 1}}.

Now consider

:<math>h(x)=x^{p-1}-1.</math>

''h'' also has degree {{nowrap|1=''p'' − 1}} and leading term {{nowrap|1=''x''<sup>''p'' − 1</sup>}}. Modulo ''p'',  [[Fermat's little theorem]] says it also has the same {{nowrap|1=''p'' − 1}} roots, 1, 2, ..., {{nowrap|1=''p'' − 1}}.

Finally, consider
:<math>f(x)=g(x)-h(x).</math>

''f'' has degree at most ''p''&nbsp;−&nbsp;2 (since the leading terms cancel), and modulo ''p'' also has the {{nowrap|1=''p'' − 1}} roots 1, 2, ..., {{nowrap|1=''p'' − 1}}. But [[Lagrange's theorem (number theory)|Lagrange's theorem]] says it cannot have more than ''p''&nbsp;−&nbsp;2 roots. Therefore, ''f'' must be identically zero (mod ''p''), so its constant term is {{nowrap|1=(''p'' − 1)! + 1 ≡ 0 (mod ''p'')}}. This is Wilson's theorem.

====Proof using the Sylow theorems====

It is possible to deduce Wilson's theorem from a particular application of the [[Sylow theorems]]. Let ''p'' be a prime. It is immediate to deduce that the [[symmetric group]] <math> S_p </math> has exactly <math>(p-1)!</math> elements of order ''p'', namely the ''p''-cycles <math> C_p </math>. On the other hand, each Sylow ''p''-subgroup in <math> S_p </math> is a copy of <math> C_p </math>. Hence it follows that the number of Sylow ''p''-subgroups is <math> n_p=(p-2)! </math>. The third Sylow theorem implies
:<math>(p-2)! \equiv 1 \pmod p.</math>
Multiplying both sides by {{nowrap|1=(''p'' − 1)}} gives
:<math>(p-1)! \equiv p-1 \equiv -1 \pmod p,</math>
that is, the result.

==Applications==

===Primality tests===
In practice, Wilson's theorem is useless as a [[primality test]] because computing (''n'' − 1)! modulo ''n'' for large ''n'' is [[Computational complexity theory|computationally complex]].<ref>Lagrange, p. 132: "cette méthode devient extrémement laborieuse, & presque impracticable"</ref>

===Quadratic residues===
Using Wilson's Theorem, for any odd prime {{nowrap|1=''p'' = 2''m'' + 1}}, we can rearrange the left hand side of
<math display="block">1\cdot 2\cdots (p-1)\ \equiv\ -1\ \pmod{p}</math>
to obtain the equality
<math display="block">1\cdot(p-1)\cdot 2\cdot (p-2)\cdots m\cdot (p-m)\ \equiv\ 1\cdot (-1)\cdot 2\cdot (-2)\cdots m\cdot (-m)\ \equiv\  -1 \pmod{p}.</math>
This becomes
<math display="block">\prod_{j=1}^m\ j^2\ \equiv(-1)^{m+1} \pmod{p}</math>
or
<math display="block">(m!)^2 \equiv(-1)^{m+1} \pmod{p}.</math>
We can use this fact to prove part of a famous result: for any prime ''p'' such that [[Pythagorean prime|''p''&nbsp;≡&nbsp;1&nbsp;(mod&nbsp;4)]], the number (−1) is a square ([[quadratic residue]]) mod ''p''.  For this, suppose ''p''&nbsp;=&nbsp;4''k''&nbsp;+&nbsp;1 for some integer ''k''.  Then we can take ''m''&nbsp;=&nbsp;2''k'' above, and we conclude that (''m''!)<sup>2</sup> is congruent to (−1) (mod ''p'').

===Formulas for primes===
Wilson's theorem has been used to construct [[Formula for primes#Formulas based on Wilson's theorem|formulas for primes]], but they are too slow to have practical value.

===p-adic gamma function===
Wilson's theorem allows one to define the [[p-adic gamma function]].

==Gauss's generalization==
[[Carl Friedrich Gauss|Gauss]] proved<ref>Gauss, DA, art. 78</ref><ref>{{cite journal
 | last1 = Cosgrave | first1 = John B.
 | last2 = Dilcher | first2 = Karl
 | journal = Integers
 | mr = 2472057
 | article-number = A39
 | title = Extensions of the Gauss–Wilson theorem
 | url = https://emis.de/journals/INTEGERS/papers/i39/i39.Abstract.html
 | volume = 8
 | year = 2008}}</ref> that
<math display=block>
\prod_{k = 1 \atop \gcd(k,m)=1}^{m-1} \!\!k \ \equiv
\begin{cases}
-1      \pmod{m}  & \text{if } m=4,\;p^\alpha,\;2p^\alpha \\
\;\;\,1 \pmod{m}  & \text{otherwise}
\end{cases}
</math>
where ''p'' represents an odd prime and <math>\alpha</math> a positive integer. That is, the product of the positive integers less than {{mvar|m}} and relatively prime to {{mvar|m}} is one less than a multiple of {{mvar|m}} when {{mvar|m}} is equal to 4, or a power of an odd prime, or twice a power of an odd prime; otherwise, the product is one more than a multiple of {{mvar|m}}.  The values of ''m'' for which the product is −1 are precisely the ones where there is a [[Primitive root modulo n|primitive root modulo ''m'']].

==See also==
*[[Wilson prime]]
*[[Table of congruences]]
*[[Agoh–Giuga conjecture]]

==Notes==
{{noteslist}}
{{Reflist}}

==References==
{{refbegin}}
The ''[[Disquisitiones Arithmeticae]]'' has been translated from Gauss's Ciceronian Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.
*English translation: {{cite book
 | last1 = Gauss
 | first1 = Carl Friedrich
 | last2 = Clarke
 | first2 = Arthur A.
 | title = Disquisitiones Arithemeticae
 | edition = 2nd corrected
 | publisher = [[Springer Science+Business Media|Springer]]
 | location = New York
 | year = 1986
 | isbn = 0-387-96254-9
}}
*German translation: {{cite book
 | last1 = Gauss
 | first1 = Carl Friedrich
 | last2 = Maser
 | first2 = H.
 | title = Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory)
 | edition = 2nd
 | publisher = Chelsea
 | location = New York
 | year = 1965
 | isbn = 0-8284-0191-8
}}
*{{cite book
 | last = Landau
 | first = Edmund
 | title = Elementary Number Theory
 | publisher = Chelsea
 | location = New York
 | year = 1966
}}.
*{{Cite book
 | last = Ore
 | first = Øystein
 | author-link = Øystein Ore
 | title = Number Theory and its History
 | publisher = Dover
 | year = 1988
 | pages = [https://archive.org/details/numbertheoryitsh0000orey/page/259 259–271]
 | isbn = 0-486-65620-9
 | url = https://archive.org/details/numbertheoryitsh0000orey/page/259
 }}
{{refend}}

==External links==
* {{springer|title=Wilson theorem|id=p/w098010}}
*{{Mathworld|urlname=WilsonsTheorem|title=Wilson's Theorem}}
* [[Mizar system]] proof: http://mizar.org/version/current/html/nat_5.html#T22
* {{Cite web |last=Ohana |first=Andrew |title=A Generalization of Wilson's Theorem |url=https://sites.math.washington.edu/~morrow/336_09/papers/Andrew.pdf}}

{{DEFAULTSORT:Wilson's Theorem}}
[[Category:Modular arithmetic]]
[[Category:Factorial and binomial topics]]
[[Category:Articles containing proofs]]
[[Category:Theorems about prime numbers]]
[[Category:Primality tests]]