Wilsons Theorem

Wilsons Theorem says, that p is prime if and only if (p-1)!+1 is a multiple of p.

To prove this, we must show, that if (p-1)!+1 is a multiple of p, that then p is prime and that if p is prime, that then (p-1)!+1 is a multiple of p.

First we will show, that p must be prime so that  (p-1)!+1 is a multiple of p. To do this we first assume, that p is not prime and that (p-1)!+1 is a multible of p. Then p can be written as x*y with x and y < p. It follows, that (p-1)! is a multible of x and y. Now we can say, that (p-1)!+1 is not a multible of x or y. It follows, that (p-1)!+1 is not a multiple of p. We also need to consider the case that x=y. It does not work for x=y=2. For all cases wit x bigger than 2, 2x will also be a factor in (p-1)!. It follows, that (p-1)!+1 is not a multiple of p. This is a contradiction which tells us, that p has to be prime.

Now we have to show the other part of the theorem. It says, that (p-1)!+1 is a multible of p for every prime p . Considering that p is prime, for every remainder modulo p there exists a unique inverse remainder, so that the product of the two remainders is 1 modulo p. The only two remainders that have them selves as a inverse are 1 and -1. The factors of (p-1)! are all possible remainders of p. It follows, that for every factor other than 1 and p-1 there exists a second factor so that when multiplied the product is congruent to 1 modulo p. The two numbers that are left multiplied together equal -1 modulo p. It follows, that (p-1)! is congruent to -1 modulo p and therefore (p-1)!+1 a multiple of p.

This proves Wilsons theorem.

Advertisements

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