# Wilson’s Theorem

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 pe – 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 2p < p2, which means that 2, p and 2p will occur in the sequence of positive integers less than n. Therefore, 2p2 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:

a2 ≡ 1 (mod n)

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

a2 – 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 12 is congruent with 1, mod n, and that -12 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.