Table of Contents

Last modified on April 26th, 2024

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:

- If (n – 1)! ≡ -1 (mod n), then n is prime
- 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.

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

Since composite numbers have more than two factors, ‘n’ can be expressed as n = n_{1} ⋅ n_{2} where 1 < n_{1}n_{2} < n

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

Also, n_{1}n_{2} < n ⇒ n_{1}n_{2} ≤ (n – 1)

Thus, 1 < n_{1}n_{2} ≤ (n – 1)

Now, n_{1 }and n_{2} are any two of the factors of (n – 1)! which is divisible by n_{1}n_{2}

Thus, (n – 1)! ≡ 0 (mod n_{1}n_{2}).

Since n = n_{1}n_{2}, (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_{1}n_{2} > 1 is another reason n = n_{1}n_{2} can not divide 1.

Thus, our assumption is wrong.

‘n’ must be a prime number.

Hence, it is proven.

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^{ −1} (mod n).

If a ≡ a^{−1} (mod n), a^{2} – 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.

**Evaluate 12! (mod 13)**

Solution:

As we know, by Wilson’s theorem, if n is a prime, then (n – 1)! ≡ -1 (mod n)

Here, n = 13 is a prime

Thus, 12! ≡ (13 – 1)! ≡ -1 (mod 13)

**Show that if n is prime, (n – 2)! ≡ 1 (mod n)**

Solution:

As we know, by Wilson’s theorem, if n is a prime, then (n – 1)! ≡ -1 (mod n)

(n – 1)! ≡ -1 ≡ (n – 1) (mod n)

On dividing by n – 1 (≠ 0), we get

(n – 2)! ≡ 1 (mod n)

Thus, if n is a prime, (n – 2)! ≡ 1 (mod n)

**Find the remainder when 171! is divided by 173.**

Solution:

As we know, by Wilson’s theorem, if n is a prime, then (n – 1)! ≡ -1 (mod n)

⇒ (n – 2)! ≡ 1 (mod n)

Here, n = 173 is a prime

Thus, 171! ≡ (173 – 2)! ≡ 1 (mod 173)

Last modified on April 26th, 2024