Wilson’s Theorem states that for an integer, **n**, where **n** is greater than 1, the product of the positive integers less than **n** is congruent with -1, mod **n**, if and only if **n** is a prime. The theorem is often stated like so:

(**n** – 1)! ≡ -1 (mod **n**)

The case when **n** is compound is easiest to prove. If **n** is compound then either **n** is the product of two unequal integers greater than 1 and less than **n**, or else **n** is the square of a prime integer.

It is clearly true that if **n** has more than one distinct prime factor that **n** is the product of two unequal integers greater than 1 and less than **n**, since if **n** has the prime factors **p** and **q** then **n** is the product of **p** and **n**/**p**, and **n**/**p** cannot be equal to **p** since **n**/**p** must be divisible by **q**. Likewise, if **n** is the power of a prime integer, **p**, with exponent **e**, and **e** is greater than 2, then **n** is the product of **p** and **p**^{e – 1}, which are unequal because **e** > 2 and therefore **e** – 1 > 1.

If **n** is the product of two unequal integers greater than 1 and less than **n**, which we can call **a** and **b**, then both of those integers will occur in the sequence of positive integers less than **n**. Therefore, (**n** – 1)! will be product of **a** and **b** and the remaining positive integers less than **n**. Because **n** is the product of **a** and **b**, **n** must divide (**n** – 1)!, from which we can conclude that (**n** – 1)! ≡ 0 (mod **n**) in this case.

If **n** is the square of a prime integer, **p**, then either **p** is 2 and **n** is 4, in which case (4 – 1)! ≡ 2 (mod 4), or else 2**p** < **p**^{2}, which means that 2, **p** and 2**p** will occur in the sequence of positive integers less than **n**. Therefore, 2**p**^{2} will divide (**n** – 1)!, from which we can conclude that with the exception of when **n** is 4, (**n** – 1)! ≡ 0 (mod **n**) in this case.

The case of when **n** is prime is also fairly simple to prove using Legrange’s Theorem which states that if **p** is a prime integer and f(**x**) is a polynomial with integer coefficients, then either every coefficient of f(**x**) is divisible by **p**, or else f(**x**) ≡ 0, mod **p**, has at most deg f(**x**) incongruent solutions.

Lagrange’s Theorem is relevant because we can use it to show that there are exactly two quadratic roots of 1, mod **n**, when **n** is prime. It is perhaps not clear why that’s relevant but I’ll get to that. If it’s not obvious why Lagrange’s Theorem means that there are exactly two quadratic roots of 1, mod **n**, I’ll explain. If **a** is a quadratic root of 1, mod **n**, **a** will satisfy this congruence:

**a**^{2} ≡ 1 (mod **n**)

We can subtract 1 from both sides which gives us this:

**a**^{2} – 1 ≡ 0 (mod **n**)

Now we can use Legrange’s Theorem to known that there can be at most 2 solutions to this congruence, given that **n** is a prime integer. Since we know that 1^{2} is congruent with 1, mod **n**, and that -1^{2} is congruent with 1, mod **n**, and **n** is prime, Legrange’s Theorem allows us to be certain that these are the only two quadratic roots of 1, mod **n**.

It happens that given a positive integer, **m**, the quadratic roots of 1, mod **m**, are exactly those integers that are congruent with their own modular multiplicative inverses, mod **m**. A modular multiplicative inverse of an integer, **a**, relatively prime to **m**, is defined such that the product of **a** and its inverse is congruent with 1, mod **m**. Furthermore, **a** can only have an inverse, mod **m**, if it is relatively prime to **m**. Given that the square of **a** is 1, mod **m**, we can conclude both that **a** is relatively prime to **m** and that **a** is its own inverse.

Another way of thinking about this is that if we start with this:

**a**^{2} ≡ 1 (mod **m**)

And then we multiply both sides of the congruence by the modular multiplicative inverse of **a**, mod **m**, we get this:

**a** ≡ **a**^{-1} (mod **m**)

So now we know, because of Legrange’s Theorem, that when **n** is a prime integer, only the integers congruent with 1 and -1, mod **n**, have inverses congruent with themselves, mod **n**. Let’s look now at why it is important to the proof of Wilson’s Theorem. First, while -1 is not in the set of positive integers less than **n**, **n** – 1 is in the set of positive integers less than **n** and **n** – 1 is congruent with -1, mod **n**.

If we examine the set of positive integers less than **n**, given that in this case **n** is a prime integer, all the positive numbers less than **n** are relatively prime to **n** and therefore each has an modular multiplicative inverse, mod **n**. Because the set of positive integers less than **n** represents exactly the reduced residue system, mod **n**, all of the positive integers less than **n** which are not congruent with their own inverse, mod **n**, are paired with exactly one other integer in the same set. Because the product of an integer and its inverse is 1, mod **n**, the product of all of these pairs is 1. Therefore, the product of all the positive integers less than **n** is congruent with the product of the two integers which are not paired with their inverse because they are congruent with their own inverse, those integers being 1 and **n** – 1. The product of these two integers is **n** – 1, which is congruent with -1, mod **n**. Thus for the case when **n** is prime:

(**n** – 1)! ≡ 1 * (**n** – 1) = **n** – 1 ≡ -1 (mod **n**)