Theorem 27: Wilson’s theorem

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 (p-1)! a^{p-1}.  (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, (p-1)! a^{p-1} \equiv (p-1)! \mod{p}.  Then we said that (p-1)! is coprime to p, so we can cancel it to get a^{p-1} \equiv 1 \mod{p}, 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.

(2-1)! = 1 \equiv 1 \mod{2}

(3-1)! = 2 \equiv 2 \mod{3}

(5-1)! = 24 \equiv 4 \mod{5}

(7-1)! = 720 \equiv 6 \mod{7}

Notice anything interesting?

It looks rather as though we have (p-1)! \equiv p-1 \mod{p}, doesn’t it?  Or, writing that another way, (p-1)! \equiv -1 \mod{p}.  And that’s Wilson’s theorem.

Theorem (Wilson) Let p be a prime.  Then (p-1)! \equiv -1 \mod{p}.

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 2 \times 6 \equiv 1 \mod{11}, so in fact we could ignore both the 2 and the 6.  Moving on, we have 3 \times 4 \equiv 1 \mod{11}, so that’s two more factors we can ignore (3 and 4).  And 5 \times 9 \equiv 1 \mod{11} and 7 \times 8 \equiv 1 \mod{11}, so in fact we’re only left with 10 \equiv -1 \mod{11}.  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 p-1 \equiv -1 \mod{p} 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 ab \equiv 1 \mod{p}.  Could we have b=a?  No, because a isn’t 1 or p-1.  (Exercise: show that if x^2 \equiv 1 \mod{p} then x \equiv \pm 1 \mod{p}.  Notice that we need p to be prime for this to work: 1^2 \equiv 3^2 \equiv 5^2 \equiv 7^2 \mod{8}.)    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 (p-1)! \equiv p-1 \equiv -1 \mod{p}, 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 (n-1)! \equiv -1 \mod{n} when n isn’t prime?  Do we always have that?

Well, we can try it.

(4-1)! = 6 \equiv 2 \mod{4}.

Ah.  So we certainly don’t always have (n-1)! \equiv -1 \mod{n}.  Is it ever true?  It turns out that (n-1)! \equiv -1 \mod{n} 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 (4-1)! (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).

Advertisements

10 Responses to “Theorem 27: Wilson’s theorem”

  1. Theorem 28: there are infinitely many Carmichael numbers « Theorem of the week Says:

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

  2. Woett Says:

    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.

  3. theoremoftheweek Says:

    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.

  4. Rob Says:

    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.

  5. theoremoftheweek Says:

    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.

  6. Rob Says:

    Thank you, theoremoftheweek.
    Appreciated.
    Rob

  7. Groups and Group Actions: Lecture 8 | Theorem of the week Says:

    […] 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. […]

  8. Groups and Group Actions: Lecture 8 | Theorem of the week Says:

    […] 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. […]

  9. Wilson's Theorem - MathHub Says:

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

  10. Groups and Group Actions: Lecture 8 | Theorem of the week Says:

    […] 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. […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: