Question

State wilson's theorem with good proof.

Answer 1

Wilson’s theorem states the following.
Let p be a prime. Then
(p − 1)! ≡ −1 (mod p).
This is obvious whenever p = 2. Hence I’ll assume from now on that p is
an odd prime.
First proof This is the one I gave in the lectures.
We use the fact that if a polynomial f(X) has integer coefficients, degree
d and there are more that d values of a ∈ {0, 1, 2, . . . , p − 1} with f(a) ≡ 0
(mod p) then all the coefficients of f are multiples of p. (It is essential that
p be prime for this to hold!)
We apply this observation to the polynomial
f(X) = X
p−1 −1−(X −1)(X −2)· · ·(X −(p−1)) = X
p−1 −1−
p
Y−1
k=1
(X −k).
If we substitute X = a for a ∈ {1, 2, . . . , p − 1} in the product above, one of
the factors becomes zero and it vanishes. Hence for a ∈ {1, 2, . . . , p − 1},
f(a) = a
p−1 − 1 ≡ 1 − 1 = 0 (mod p)
by Fermat’s little theorem. The degree of f is less than p−1 as the coefficient
of Xp−1
is 1 − 1 = 0. As there are p − 1 solutions of f(a) ≡ 0 (mod p) in
{1, 2, . . . , p − 1}, then all the coefficients of f are divisible by p. It follows
that f(0) ≡ 0 (mod p), that is
0 ≡ −1 −
p
Y−1
k=1
(−k) = −1 − (−1)p−1
p
Y−1
k=1
k = −1 − (p − 1)! (mod p)
(noting that as p is odd, (−1)p = 1.) Rearranging gives
(p − 1)! ≡ −1 (mod p).
Second proof This is the most common textbook proof.
Each a in {1, 2, . . . , p − 1} has an inverse a
∗ ∈ {1, 2, . . . , p − 1} modulo
p, that is aa∗ ≡ 1 (mod p). This inverse is unique and it follows that
(a
∗
)
∗ = a. If a = a
∗
then 1 ≡ aa∗ = a
2
(mod p). We have seen that this tonecessitates a ≡ ±1 (mod p) and so a = 1 or a = p − 1. In the product
(p − 1)! = 1 × 2 × 3 × · · · × (p − 2) × (p − 1) we pair off each term, save for 1
and p − 1 with its inverse modulo p. We thus get (p − 1)! ≡ 1 × (p − 1) ≡ −1
(mod p).
As an illustration, consider the case p = 11. Then
10! = 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 × 10
= 1 × (2 × 6) × (3 × 4) × (5 × 9) × (7 × 8) × 10
≡ 1 × 1 × 1 × 1 × 1 × 10 = 10 ≡ −1 (mod 11).
Third proof This requires the fact that each prime has a primitive root.
Let g be a primitive root modulo p. Then the numbers 1, g, g
2
, . . . , gp−2
are congruent modulo p, in some order, to 1, 2, . . . , p − 1. Hence
(p − 1)! ≡ 1gg2
· · · g
p−2 = g
1+2+···+(p−2) (mod p).
The sum 1 + 2 + · · · + (p − 2) is the sum of an arithmetic progression with
p − 2 terms, and so equals
(p − 2)(p − 2) + 1
2
=
(p − 2)(p − 1)
2
.
Hence
(p − 1)! ≡ g
(p−2)(p−1)/2
(mod p).
To analyse this further, recall that p is odd. Thus p = 2k + 1 where k is a
natural number. As k < 2k = p − 1 then g
k 6≡ 1 (mod p) but g
2k = g
p−1 ≡ 1
(mod p) by Fermat’s little theorem. As (g
k
)
2 = g
2k ≡ 1 (mod p) then
g
k ≡ ±1 (mod p) and so g
k ≡ −1 (mod p).
We finally conclude that
(p − 1)! ≡ g
(p−2)(p−1)/2 = g
(2k−1)k = (g
k
)
2k−1 ≡ (−1)2k−1 = −1 (mod p).

Answer 2

Wilson's theorem states that (P-1)!≡ -1 mod p where p is a prime number.