Wilson's Theorem

Date: 03/03/2002 at 10:37:44
From: Hanneke de Boer
Subject: Prime numbers

I'm looking for a proof for Wilson's theorem:

n divides (n-1)! + 1 if and only if n is a prime number.

Can you help me?
Thank you in advance,
Hanneke de Boer

Date: 03/04/2002 at 14:13:39
From: Doctor Floor
Subject: Re: Prime numbers

Hi, Hanneke,

Thanks for your question.

Let us consider all numbers 1,2,3,...,p-1. Take a number x from them.

From Fermat's Little theorem we know that x^(p-1) == 1 (mod p), see 
from the Dr. Math archive

  Fermat's Little Theorem
  http://mathforum.org/dr.math/problems/heden.9.2.00.html   

This means that there must be some smallest m <= p-1 such that 
x^m = 1 and m is a divisor of p-1. In that case we know that 
x*x^(m-1)==1 (mod p). In most cases x and x^(m-1) are different 
numbers, but this is clearly not the case when x = 1 and x = p-1... 
If x and x^(m-1) are different, then there is a y in the numbers 
1,2,3,...,p-1,p-2 such that y==x^(m-1) (mod p). So we have a 
pair (x,y) from 1,2,3,...,p-1 with x*y==1 (mod p).

For all numbers from 2,3,...,p-2 except we find the pairs that have a 
product of 1 modulo p. Clearly the numbers are exactly divided into 
these pairs. Adding 1 and p-1, we see that the product

  1*2*...*(p-2)*(p-1) == -1 (mod p)

and thus that (p-1)!+1 is divisable by p.

For the converse ("and only if"), it is enough to note that if x is 
composite, than we can find 1<y<p such that y is a divisor of x. 
Clearly y is a divisor of (x-1)!, and not a divisor of (x-1)!+1. But 
if x would have been a divisor of (x-1)!+1, then y should have been so 
as well. We have a contradiction and that proves the converse.

If you have more questions, just write back.

Best regards,
- Doctor Floor, The Math Forum
  http://mathforum.org/dr.math/