Mathematics, Number Theory

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.

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

a2 ≡ 1 (mod m)

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

aa-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)

Leave a Reply

Your email address will not be published. Required fields are marked *