Wilson’s Theorem

Wilson’s theorem states that any positive integer, n (> 1), is a prime number if and only if (n – 1)! ≡ -1 (mod n), which means:

1. If (n – 1)! ≡ -1 (mod n), then n is prime
2. If n is prime, then (n – 1)! ≡ -1 (mod n), the converse

It is used in mathematical calculations in elementary number theory involving (n – 1)!. Wilson’s theorem is also used in fields like cryptography for coding-decoding.

Proof

Proving: If (n – 1)! ≡ -1 (mod n), then n is prime

If possible, let ‘n’ be a composite number.

Since composite numbers have more than two factors, ‘n’ can be expressed as n = n₁ ⋅ n₂ where 1 < n₁n₂ < n

Now, (n – 1)! = (n – 1)(n – 2)(n – 3)…3 ⋅ 2 ⋅ 1

Also, n₁n₂ < n ⇒ n₁n₂ ≤ (n – 1)

Thus, 1 < n₁n₂ ≤ (n – 1)

Now, n₁ and n₂ are any two of the factors of (n – 1)! which is divisible by n₁n₂

Thus, (n – 1)! ≡ 0 (mod n₁n₂). 

Since n = n₁n₂, (n – 1)! ≡ 0 (mod n)……………..(i)

Given that (n – 1)! ≡ -1 (mod n)………….(ii)

This implies 0 ≡ -1 (mod n)

⇒ 0 + 1 ≡ 0 (mod n)

⇒ 1 ≡ 0 (mod n) means if we divide 1 by ‘n,’ the remainder will be 0.

⇒ n|1, which contradicts as ‘n’ is a composite number (by our assumption), and 1 can not be divisible by any composite number. 

Also, n₁n₂ > 1 is another reason n = n₁n₂ can not divide 1.

Thus, our assumption is wrong.

‘n’ must be a prime number.

Hence, it is proven.

Proving: If n is prime, then (n – 1)! ≡ -1 (mod n), the Converse

The converse of Wilson’s theorem can be proved in two ways.

1. Elementary Proof

Let ‘n’ be a prime number.

For the smallest prime number, n = 2: 1! ≡ -1 (mod 2). 

If n > 2, then for any a Є [1, n – 1], there exists b Є [1, n – 1], such that ab ≡ 1 (mod n)

Each integer a Є {1, …, n – 1} has an inverse in modulo n. 

This inverse is unique and denoted by a ⁻¹ (mod n). 

If a ≡ a⁻¹ (mod n), a² – 1 ≡ 0 (mod n) 

⇒ (a − 1)(a + 1) ≡ 0 (mod n), which has two roots in modulo n: a ≡ 1 (mod n) and a ≡ -1 (mod n) 

⇒ a = 1 or a = n – 1

We can arrange all the integers 1, 2, …, n – 1, except for 1 and n – 1, into pairs {a, b}, such that ab ≡ 1 (mod n) except for 1 and n – 1 whose product is -1 (mod n).

Thus, (n – 1)! ≡ 1 ⋅ (n – 1) ≡ -1 (mod n).

2. Algebraic Proof

Let ‘n’ be a prime number.

Considering the field of integers in modulo n, by Fermat’s little theorem, we know: 

Every non-zero element of this field is a root of the polynomial f(x) = x^{n – 1} – 1.

Since the field has only n – 1 non-zero elements, which follows that ${x^{n-1}-1=\prod ^{n-1}_{r=1}\left( x-r\right)}$

Now, either n = 2 or n – 1 is even.

For n = 2, a ≡ -a (mod 2) for any integer a,

For n – 1, (-1)^{n – 1} ≡ 1 (mod n) 

Thus, x^{n-1}-1=\prod ^{n-1}_{r=1}\left( x-r\right) =\prod ^{n-1}_{r=1}\left( -x+r\right)

By putting x = 0, we get (n – 1)! ≡ -1 (mod n)

Hence, it is proven.

Solved Examples