Associated Topics || Dr. Math Home || Search Dr. Math

### 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?
Hanneke de Boer
```

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

Hi, Hanneke,

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/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search