Wilson's Theorem

Theorem

Ifis prime then

Proof: Sinceandwe can concentrate on Consider the set ofintegersIfthen asthe congruencehas a unique solutionLet the solution beso thatNowfor that would givecontradicting Similarlyfor that would implyagain contradictinghence a' in S.

Finallyfor otherwisewhich implies thatdivides sodivides eitherorby Euclid's Lemma which amount toorrespectively, both of which contradict that

Hence for eachthere issuch thatso the elements offormdistinct pairsandwithMultiplying these congruences together, each element ofappears exactly once so

Now multiply both sides byto giveand so

The converse of Wilson's theorem is also true: Ifthen n is prime.

Proof: Suppose thatdividesLetbe a positive divisor ofthenso thatdividesBut dividesso dividessohas no divisors other than 1 andso is prime.

To illustrate Wilson's Theorem, consider

We pair the numbers 2 to 15:

Henceand

Example: Find the smallest prime divisor of

By Wilson's theorem,dividesand no smaller prime does, because it would dividehence 1.