Wilson's theorem

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 integers less than ''n'' is one less than a multiple of ''n''. That is (using the notations of modular arithmetic), the factorial $(n - 1)! = 1 \times 2 \times 3 \times \cdots \times (n - 1)$ satisfies

:$(n-1)!\ \equiv\; -1 \pmod n$

exactly when ''n'' is a prime number. In other words, any number ''n'' is a prime number if, and only if, (''n'' − 1)! + 1 is divisible by ''n''.

History

This theorem was stated by Ibn al-Haytham (c. 1000 AD), and, in the 18th century, by John Wilson. Edward Waring announced the theorem in 1770, although neither he nor his student Wilson could prove it. Lagrange gave the first proof in 1771. There is evidence that Leibniz was also aware of the result a century earlier, but he never published it.

Example

For each of the values of ''n'' from 2 to 30, the following table shows the number (''n'' − 1)! and the remainder when (''n'' − 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 prime values of ''n'', gold for composite values.

Proofs

The proofs (for prime moduli) below use the fact that the residue classes modulo a prime number are a field—see the article prime field for more details. Lagrange's theorem, which states that in any field a polynomial of degree ''n'' has at most ''n'' roots, is needed for all the proofs.

Composite modulus

If ''n'' is composite it is divisible by some prime number ''q'', where . Because $q$ divides $n$, let $n = qk$ for some integer $k$. Suppose for the sake of contradiction that were congruent to where n is composite. Then (n-1)! would also be congruent to −1 (mod ''q'') as $(n-1)! \equiv -1 \ (\text \ n)$ implies that $(n-1)! = nm - 1 = (qk)m - 1 = q(km) - 1$ for some integer $m$ which shows (n-1)! being congruent to -1 (mod q). But (''n'' âˆ’ 1)! â‰¡ 0 (mod ''q'') by the fact that q is a term in (n-1)! making (n-1)! a multiple of q. A contradiction is now reached.

In fact, more is true. With the sole exception of 4, where 3! = 6 â‰¡ 2 (mod 4), if ''n'' is composite then (''n'' âˆ’ 1)! is congruent to 0 (mod ''n''). The proof is divided into two cases: First, if ''n'' can be factored as the product of two unequal numbers, , where 2 â‰¤ ''a'' < ''b'' â‰¤ ''n'' âˆ’ 2, then both ''a'' and ''b'' will appear in the product and (''n'' âˆ’ 1)! will be divisible by ''n''. If ''n'' has no such factorization, then it must be the square of some prime ''q'', ''q'' > 2. But then 2''q'' < ''q''² = ''n'', both ''q'' and 2''q'' will be factors of (''n'' âˆ’ 1)!, and again ''n'' divides (''n'' âˆ’ 1)!.

Prime modulus

Elementary proof

The result is trivial when , so assume ''p'' is an odd prime, . Since the residue classes (mod ''p'') are a field, every non-zero ''a'' has a unique multiplicative inverse, ''a''^−1. Lagrange's theorem implies that the only values of ''a'' for which are (because the congruence can have at most two roots (mod ''p'')). Therefore, with the exception of ±1, the factors of can be arranged in disjoint pairs such that product of each pair is congruent to 1 modulo ''p''. This proves Wilson's theorem.

For example, for , one has
10! = 1\cdot10)cdot 2\cdot6)(3\cdot4)(5\cdot9)(7\cdot8) \equiv 1cdot \cdot1\cdot1\cdot1 \equiv -1 \pmod.

Proof using Fermat's little theorem

Again, the result is trivial for ''p'' = 2, so suppose ''p'' is an odd prime, . Consider the polynomial

:$g(x)=(x-1)(x-2) \cdots (x-(p-1)).$

''g'' has degree , leading term , and constant term . Its roots are 1, 2, ..., .

Now consider

:$h(x)=x^-1.$

''h'' also has degree and leading term . Modulo ''p'', Fermat's little theorem says it also has the same roots, 1, 2, ..., .

Finally, consider
:$f(x)=g(x)-h(x).$

''f'' has degree at most ''p'' âˆ’ 2 (since the leading terms cancel), and modulo ''p'' also has the roots 1, 2, ..., . But Lagrange's theorem says it cannot have more than ''p'' âˆ’ 2 roots. Therefore, ''f'' must be identically zero (mod ''p''), so its constant term is . 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 $S_p$ has exactly $(p-1)!$ elements of order ''p'', namely the ''p''-cycles $C_p$. On the other hand, each Sylow ''p''-subgroup in $S_p$ is a copy of $C_p$. Hence it follows that the number of Sylow ''p''-subgroups is $n_p=(p-2)!$. The third Sylow theorem implies
:$(p-2)! \equiv 1 \pmod p.$
Multiplying both sides by gives
:$(p-1)! \equiv p-1 \equiv -1 \pmod p,$
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 computationally complex, and much faster primality tests are known (indeed, even trial division is considerably more efficient).

Used in the other direction, to determine the primality of the successors of large factorials, it is indeed a very fast and effective method. This is of limited utility, however.

Quadratic residues

Using Wilson's Theorem, for any odd prime , we can rearrange the left hand side of
$1\cdot 2\cdots (p-1)\ \equiv\ -1\ \pmod$
to obtain the equality
$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.$
This becomes
$\prod_^m\ j^2\ \equiv(-1)^ \pmod$
or
$(m!)^2 \equiv(-1)^ \pmod.$
We can use this fact to prove part of a famous result: for any prime ''p'' such that ''p'' â‰¡ 1 (mod 4), the number (−1) is a square (quadratic residue) mod ''p''. For suppose ''p'' = 4''k'' + 1 for some integer ''k''. Then we can take ''m'' = 2''k'' above, and we conclude that (''m''!)² is congruent to (−1).

Formulas for primes

Wilson's theorem has been used to construct 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' generalization

Gauss’ generalization of Wilson’s Theorem states that if $n$ is four, an odd prime power, or twice an odd prime power, then the product of relatively prime integers less than itself add one is divisible by $n$. It goes further to say that otherwise, the same product subtract one is divisible by $n$.

To state Gauss' Generalization of Wilson's Theorem, we use the Euler's totient function, denoted $\varphi(n)$, which is defined as the number of positive integers less than or equal to $n$ which are also relatively prime with $n$. Let's call such numbers $a_i$, where $\gcd(a_i,n)=1$.

Gauss proved given an odd prime $p$ and some integer $\alpha>0$, then

:$\prod_^ \!\!a_k \ = \begin -1 \pmod n & \text n=4,\;p^\alpha,\;2p^\alpha \\ \;\;\,1 \pmod n & \text \end$.
First, let's us note this is the proof for cases $n>2$, since the results are trivial for $n =\$.

For all $a_i$, we know there exist some $a_j$, where $i\neq j$ and $\gcd(a_j,n)=1$, such that $a_ia_j=1$. This allows us to pair each of the elements together with its inverse. We are left now with $a_i$ being its own inverse. So in other words $a_i$ is a root of $f(x)=x^2-1$ in $\Z/n\Z$, and $f(x)=(x-1)(x+1)$, in the polynomial ring
\Z/n\Z
. If $a_i$ is a root, it follows that $n-a_i$ is also a root. Our objective is to show that the number of roots is divisible by four, unless $n=4, n=p^\alpha$, or $n = 2p^\alpha$.

Let's consider $n=2$. Then we notice we have one root since $1\equiv-1\pmod2$.

Consider $n=4$. Then, it is clear there are two roots, specifically, $x\equiv1\pmod4$ and $x\equiv-1\pmod4$.

Say $n=p^\alpha$. It is again clear there are two solutions.

We now consider $n=2^\beta, \beta>2$. If one of the factors of $f(x)$ is divisible by 2, so is the other. Take the factor $(x+1)$ to be divisible by $2^1$. Then, it follows that there are 4 distinct roots of $f(x)$, namely $x\equiv1\pmod n$, $x\equiv1+2^\pmod n$, $x\equiv-1\pmod n$, and $x\equiv-1-2^\pmod n$, when $n=2^\beta, \beta>2$.

Finally, let's look at the general case where $n=2^\beta p_1p_2\dots p_k$. We find 2 roots of $f(x)$ over each $\Z/2^\beta\Z$ and $\Z/p_r^\Z$, except when $\beta>2$. Using the Chinese remainder theorem, we find that when $n$ is not divisible by 2, we have a total of $2^k$ solutions of $f(x)$. Assuming $\beta=1$, in $\Z/2\Z$, we have one root, so we still have a total of $2^k$ solutions. When $\beta=2$, we have 4 roots in $\Z/4\Z$, so there are a total of $2^$ roots of $f(x)$. For all cases where $\beta>2$, there are 4 roots in $\Z/2^\beta\Z$ with a total of $2^$ solutions. This shows that the number of roots are divisible by 4, unless $n=4, n=p^\alpha$, or $n=2p^\alpha$.

Say $a_i$ is a root of $f(x)$ in $\Z/n\Z$. Then $a_i(n-a_i)=-a_i^2=-1$. So, if the number of roots of $f(x)$ is divisible by 4, then we can say the product of the roots if 1. Otherwise, we can say the product is -1. So we can conclude that

$\prod_^ \!\!a_k \ = \begin -1 \pmod n & \text n=4,\;p^\alpha,\;2p^\alpha \\ \;\;\,1 \pmod n & \text \end$.

See also

*Wilson prime
*Table of congruences

Notes

References

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

External links

*
*
* Mizar system proof: http://mizar.org/version/current/html/nat_5.html#T22
*

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