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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.