algebra Algebra is a branch of mathematics that deals with abstract systems, known as algebraic structures, and the manipulation of expressions within those systems. It is a generalization of arithmetic that introduces variables and algebraic ope ...

and

number theory Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...

, Wilson's theorem states that a

natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...

''n'' > 1 is a

prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...

if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...

the product of all the

positive integer In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positiv ...

s less than ''n'' is one less than a multiple of ''n''. That is (using the notations of

modular arithmetic In mathematics, modular arithmetic is a system of arithmetic operations for integers, other than the usual ones from elementary arithmetic, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to mo ...

), the

factorial In mathematics, the factorial of a non-negative denoted is the Product (mathematics), product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times ...

(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 integer ''n'' > 1 is a prime number if, and only if, (''n'' − 1)! + 1 is divisible by ''n''.

History

The theorem was first stated by

Ibn al-Haytham Ḥasan Ibn al-Haytham (Latinization of names, Latinized as Alhazen; ; full name ; ) was a medieval Mathematics in medieval Islam, mathematician, Astronomy in the medieval Islamic world, astronomer, and Physics in the medieval Islamic world, p ...

. Edward Waring announced the theorem in 1770 without proving it, crediting his student John Wilson for the discovery.

Lagrange Joseph-Louis Lagrange (born Giuseppe Luigi LagrangiaLeibniz was also aware of the result a century earlier, but 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

, 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

As a biconditional (if and only if) statement, the proof has two halves: to show that equality ''does not'' hold when

n

is composite, and to show that it ''does'' hold when

n

is prime.

Composite modulus

Suppose that

n

is composite. Therefore, it is divisible by some prime number

q

where

2 \leq q < n

. Because

q

divides

n

, there is an integer

k

such that

n = qk

. Suppose for the sake of contradiction that

(n-1)!

were congruent to

-1

modulo

. Then

(n-1)!

would also be congruent to

-1

modulo

: indeed, if

(n-1)! \equiv -1 \pmod

then

(n-1)! = nm - 1 = (qk)m - 1 = q(km) - 1

for some integer

m

, and consequently

(n-1)!

is one less than a multiple of

q

. On the other hand, since

2 \leq q \leq n - 1

, one of the factors in the expanded product

(n - 1)! = (n - 1) \times (n - 2) \times \cdots \times 2 \times 1

q

. Therefore

(n - 1)! \equiv 0 \pmod

. This is a contradiction; therefore it is not possible that

(n - 1)! \equiv -1\pmod

when

n

is composite. In fact, more is true. With the sole exception of the case

n = 4

, where

3! = 6 \equiv 2 \pmod

, if

n

is composite then

(n - 1)!

is congruent to 0 modulo

n

. The proof can be divided into two cases: First, if

n

can be factored as the product of two unequal numbers,

n = ab

, where

2 \leq a < b < n

, then both

a

and

b

will appear as factors in the product

(n - 1)! = (n - 1)\times (n - 2) \times \cdots \times 2 \times 1

and so

(n - 1)!

is divisible by

ab = n

. If

n

has no such factorization, then it must be the square of some prime

q

larger than 2. But then

2q < q^2 = n

, so both

q

and

2q

will be factors of

(n-1)!

, and so

n

divides

(n-1)!

in this case, as well.

Prime modulus

The first two proofs below use the fact that the

residue class In mathematics, modular arithmetic is a system of arithmetic operations for integers, other than the usual ones from elementary arithmetic, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to mod ...

es modulo a prime number form a

finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...

(specifically, a

prime field In mathematics, a field is a set on which addition, subtraction, multiplication, and division are defined and behave as the corresponding operations on rational and real numbers. A field is thus a fundamental algebraic structure which is wid ...

Elementary proof

The result is trivial when

p = 2

, so assume

p

is an odd prime,

p \geq 3

. Since the residue classes modulo

p

form a field, every non-zero residue

a

has a unique multiplicative inverse

a^

Euclid's lemma In algebra and number theory, Euclid's lemma is a lemma that captures a fundamental property of prime numbers: For example, if , , , then , and since this is divisible by 19, the lemma implies that one or both of 133 or 143 must be as well. In ...

implies that the only values of

a

for which

a \equiv a^\pmod

are

a \equiv \pm 1 \pmod

. Therefore, with the exception of

\pm 1

, the factors in the expanded form of

(p - 1)!

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

p = 11

, one has

\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 In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric grou ...

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.

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

(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 In number theory, an integer ''q'' is a quadratic residue modulo operation, modulo ''n'' if it is Congruence relation, congruent to a Square number, perfect square modulo ''n''; that is, if there exists an integer ''x'' such that :x^2\equiv q \pm ...

) mod ''p''. For this, 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) (mod ''p'').

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's generalization

Gauss Johann Carl Friedrich Gauss (; ; ; 30 April 177723 February 1855) was a German mathematician, astronomer, Geodesy, geodesist, and physicist, who contributed to many fields in mathematics and science. He was director of the Göttingen Observat ...

proved that

\prod_^ \!\!k \ \equiv
\begin
-1      \pmod  & \text m=4,\;p^\alpha,\;2p^\alpha \\
\;\;\,1 \pmod  & \text
\end

where ''p'' represents an odd prime and

\alpha

a positive integer. That is, the product of the positive integers less than and relatively prime to is one less than a multiple of when 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 . The values of ''m'' for which the product is −1 are precisely the ones where there is a primitive root modulo ''m''.

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. *English translation: *German translation: *. *

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