Wilson's Theorem



Wilson's theorem states that if p prime then p divides (p-1)! + 1.
In order to prove this we are first going to proof that given GCD(r,s)=1 an x and y exist such that rx + sy = 1
This proof is a variation on the proofs in text books, so it may be unique.

Terminology: a | b will means a divides b, and a==b mod(c) will means a is congruent to b mod c or c | a-b
Terminology: GCD means greatest common dividor

Proof 1 : Prove that rx + sy = 1 follows:
So r k== a mod (s) where k>=1 and k<=s-1 and k integer
Suppose we have rk1 == a mod (s) and rk2== a mod (s)
Then we have that rk1 - r r k== s+i mod (s)== 0 mod (s), So r( k1- k2)==0 mod (s)
But this means that s | r or s | k1- k2 , which is not true.
Therefore for each k we will also find a different a.
Now suppose a = s , but then s | r which cannot be.
Suppose that a > s, then we have a = st + i where i smaller than s, so that r k == st + i mod (s) , but then r k== i mod (s), so a is always smaller than s
Because we find a different a for each k , and k is from 1 to s-1 we will also have s-1 different a's in some order.
As a>0 and a smaller than s , it follows then that for some k their will be an a such that a = 1
Therefore we have rkj == 1 mod (s)
This means s | rkj-1 or sz = rkj-1, or rkj - sz = 1, now let kj = x and -z = y and we have rx + sy = 1


Now we use this proof to prove Wilson's theorem

Let p be prime and let k > 1 and k< = p-2.
Now let k run from 2 to p-2 and let us form the following mod operations in order ka == 1 mod p.
Note that 1 == 1 mod p and p == 0 mod p
So we have 2a2 == 1 mod p , 3a3 == 1 mod p , 4a4 == 1 mod p and so on up to (p-2)ap-2 == 1 mod p
Notice in the cases above that each a will be unique as in proof 1. Because each a is unique it follows that in some order they will be from 2 to p-2
Now we form products of these mod operations 2a2 x 3a3 x ....x (p-2)ap-2 == 1 mod p
As we form our product starting from k = 2 and we encounter a duplicate set along the way, we leave that duplicate out of the product.
That is if we encounter an mod operation rt == 1 mod p, where this set was in the form tr == 1 mod p for t < r and already in the product so far formed,
we leave r t== 1 mod p out of our product, because tr == 1 mod p is already in the product
Our product will thus be 2 x 3 x 4....(p-2 ) == 1 mod p , So (p-2)! == 1 mod p , so (p-1)! == 1(p-1) mod p
So (p-1)! == -1 mod p , so p | (p-1)! + 1