Tag Archives: prime

Fermat’s little Theorem

Fermat’s little theorem: Let p be a prime. Then a^p-a is a multiple of p. In other words a^p is congruent to a mod p.

Proof: We will use Induction. For a=1 we have a^p-a=1^p-1=1-1=0. 0 is a multiple of p.

Now we assume, that the theorem works for a.

Last but not least, we have to show that a+1 works.  We have  (a+1)^p-(a+1)=(a+1)^p-a-1. Now we use the binomial theorem:

Screen Shot 2014-12-20 at 11.52.24 AM

We know that a^p-a is a multiple of p. Every summand of the sum is a multiple of p as well. It follows, that the theorem works for a+1 as well.

This proves the theorem.

Advertisements

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.