Last modified on February 15th, 2024

chapter outline

 

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 = n1 ⋅ n2 where 1 < n1n2 < n

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

Also, n1n2 < n ⇒ n1n2 ≤ (n – 1)

Thus, 1 < n1n2 ≤ (n – 1)

Now, n1 and n2 are any two of the factors of (n – 1)! which is divisible by n1n2

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

Since n = n1n2, (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, n1n2 > 1 is another reason n = n1n2 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 −1 (mod n). 

If a ≡ a−1 (mod n), a2 – 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) = xn – 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

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)

Comments are closed.