Quite a quick theorem this week, I think.

In the first proof I gave of Fermat’s little theorem, I suggested multiplying together the p-1 numbers a, 2a, …, (p-1)a (where a is coprime to the prime p), to get . (As usual, I’m writing (p-1)! for p-1 factorial.) But, as we saw, those p-1 numbers are congruent to 1, 2, …, p-1 (mod p) (in some order), so this product is congruent to (p-1)!. That is, . Then we said that (p-1)! is coprime to p, so we can cancel it to get , which is Fermat’s little theorem. But could we have said any more about the quantity (p-1)! (more than that it is coprime to p)?

Let’s try some examples.

Notice anything interesting?

It looks rather as though we have , doesn’t it? Or, writing that another way, . And that’s Wilson’s theorem.

**Theorem (Wilson)** Let be a prime. Then .

How can we prove this? Let’s try to understand why it’s true for the examples above. For the small primes, it was pretty easy. I stopped with 6! because I didn’t much feel like computing 10!. But could we have found 10! (mod 11) without computing 10!? (I’m sorry that punctuation looks so wrong with factorial signs!)

Let’s see. We have (11-1)! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10. We can ignore the 1 at the front. Looking at the next factor, I notice that , so in fact we could ignore both the 2 and the 6. Moving on, we have , so that’s two more factors we can ignore (3 and 4). And and , so in fact we’re only left with . Ah, so that was actually pretty easy. We never had to work out 10!.

Can we use this idea in general?

Yes! Let’s imagine we’ve written out (p-1)!, and let’s pick some factor a in it. We can ignore 1 again, and we’d like to be left with at the end, so let’s assume that a isn’t 1 or p-1. Then a is some number coprime to p, so it has an inverse. That is, there’s some b so that . Could we have b=a? No, because a isn’t 1 or p-1. (Exercise: show that if then . Notice that we need p to be prime for this to work: .) So we can pair a with b, and so ignore those two factors (just as we paired 2 with 6 and so on in our example with p=11 above).

But we can do this for each factor a that isn’t 1 and p-1. So when we work out (p-1)! (mod p), all the factors pair off except 1 and p-1, so we just get left with , as we wanted.

Where do we go from here? A natural question would be to ask whether we needed p to be prime. Do we ever have when n isn’t prime? Do we *always* have that?

Well, we can try it.

.

Ah. So we certainly don’t always have . Is it ever true? It turns out that if and only if n is prime.

In fact, this isn’t too hard to see. In our example above, we had a non-trivial divisor of 4 (namely 2), and that divides (because 2 occurs as one of the factors), so we couldn’t possibly hope that 4 would divide (4-1)! + 1 (because 2 doesn’t divide 1).

In general, say that n is composite, and that d is a non-trivial divisor (it’s not 1 or n). Then d divides (n-1)! (because d occurs as one of the factors), but d does not divide 1, so d does not divide (n-1)! + 1, so n does not divide (n-1)! + 1.

In theory, we could use this fact to check whether a number is prime. I give you a huge number n (100 digits, or something), and all you have to do is compute (n-1)! (mod n) and see whether it’s -1. In practice, though, this would be a terrible idea, because computing (n-1)! (mod n) would take a *very* long time. So Wilson’s theorem doesn’t have a practical application to primality testing, but I think it’s a pretty result (with a pretty proof) nonetheless.

It also has an interesting history, as I discovered when reading a brief biography of Wilson. A nice link to Waring, of Waring’s problem fame.

### Further reading

Not a huge amount to say here, except to give my traditional plug for *The Higher Arithmetic* by Davenport. (I don’t get commission for saying that!) The Wikipedia page has another proof (quite a nice one).

June 3, 2010 at 11:37 am

[…] Theorem of the week Expositions of interesting mathematical results « Theorem 27: Wilson’s theorem […]

July 14, 2010 at 12:23 am

Maybe somewhat neater would be not only stating that n is not a divisor of (n-1)! + 1 for n composite, but showing that n, if composite, is actually a divisor of (n-1)!, as long as n > 4;

Let n = a^2 > 4 (so that n > 2a). Then n is a divisor of a*(2a) which is a divisor of (n-1)!.

Let n = ab with 1 < a < b < n. Then n is a divisor of a*b, which divides (n-1)!

And since those 2 cases cover every composite number, we're done.

July 14, 2010 at 7:32 am

Thanks, Woett. I was trying to keep my post fairly short, which is why I didn’t go into this, but it’s nice to have your argument in the comments.

August 25, 2013 at 10:18 pm

Hi, I would lik to know where can I find the proof of this: Let (n,k) denote the usual factorial (choose k among n).

If (n,1)=(n,2)=…=(n,n-1)=0 (mod p), then there exists t such that n=p^t.

Any suggestion is greatly appreciated.

Rob.

August 26, 2013 at 6:54 am

Rob, I recommend Ask NRICH — it’s a free discussion forum run by the University of Cambridge where you can ask mathematical questions and others will help you to answer them.

August 26, 2013 at 1:55 pm

Thank you, theoremoftheweek.

Appreciated.

Rob

March 13, 2015 at 11:57 am

[…] Let be a prime. Which elements of (a group under multiplication) are self-inverse ()? What are the equivalence classes for the equivalence relation from the last paragraph when applied to this group? What does this tell us about the product modulo ? The result here is called Wilson‘s theorem; you can read more about it in Richard Earl’s online notes, or in my blog post. […]

March 10, 2016 at 2:26 pm

[…] Let be a prime. Which elements of (a group under multiplication) are self-inverse (have )? What are the equivalence classes for the equivalence relation from the last paragraph when applied to this group? What does this tell us about the product modulo ? The result here is called Wilson‘s theorem; you can read more about it in Richard Earl’s online notes, or in my blog post. […]

March 18, 2016 at 1:06 am

[…] need help understanding Wilson’s Theorem. I was reading a post on this blog explaining this […]

March 9, 2017 at 10:01 am

[…] Let be a prime. Which elements of (a group under multiplication) are self-inverse (have )? What are the equivalence classes for the equivalence relation from the last paragraph when applied to this group? What does this tell us about the product modulo ? The result here is called Wilson‘s theorem; you can read more about it in Richard Earl’s online notes, or in my blog post. […]