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]