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:
Example: Find the smallest prime divisor of
By Wilson's theorem,dividesand no smaller prime does, because it would dividehence 1.