Editing Wilson's theorem (section)

==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.