wilson'stheorem

Wilson's Theorem

(p-1)! + 1==0 [mod p][p prime]

Proof:

Evidently true for p=2,3

Suppose p>3:

Consider the congruence aa’==1 [mod p]

Arrange the p-3 integers 2,3,…p-2 into pairs aa’ (a<>a’) == 1 [mod p] [Lemma 1]

The product of all these pairs will also == 1 [mod p]

Finally multiply by the remaining pair of factors, 1 and p-1 to give:

(p-1)!==p-1 [mod p]

Converse:

Suppose (n-1)! + 1==0 [mod n][d|n][d<>n]

d<=n-1, so d|(n-1)!

But n|((n-1)! + 1), so d|((n-1)! + 1) => d|1 => n prime

LEMMA 1

aa’==1 [mod p]

hcf (a,p)=1 [a<>0 mod p]

Therefore ax + py = 1, for some x, y

So, a’==x always exists

If a**2==1 [mod p]

a**2 - 1=(a+1)(a-1)==0 [mod p]

By Lagrange’s Theorem, this has only two solutions, clearly a==+/- 1 [mod p]

Therefore, in general, a<>a’ [mod p]