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