BIGtheme.net http://bigtheme.net/ecommerce/opencart OpenCart Templates
Friday , July 28 2017
Home / Elementary Number Theory / Wilson’s theorem of number theory

Wilson’s theorem of number theory

Proof: Dismissing the case p = 2 and p = 3 as being evident, let us take p > 3. Suppose that a is any of the p – 1 positive integers

1, 2, 3, … , p – 1

and consider the linear congruence ax ≡ 1 (mod p) . Then gcd(a, p) = 1. By linear congruence theorem , this congruence admits a unique solution modulo p; hence, there is a unique integer aʹ , with 1 ≤ aʹ ≤ p – 1 , satisfying aaʹ ≡ 1 (mod p).

Because p is prime, a = a ʹ if and only if a = 1 or a = p – 1 . Indeed, the congruence a 2 ≡ 1 (mod p) is equivalent to (a – 1). (p + 1) ≡ 0 (mod p). Therefore either a – 1 ≡ 0 (mod p), in which case a = 1 or a + 1 ≡ 0 (mod p), in which case

a = p – 1.

If we omit the numbers 1 and p – 1 , the effect is to group the remaining integers 2, 3, … , p – 1 into pairs a, aʹ, where a ≠ aʹ, such that there product aaʹ ≡ 1 (mod p). When these (p – 3 ) / 2 congruence are multiplied together and factors rearranged, we get

  1. 3….(p – 2 ) ≡ 1 (mod p)

Or rather

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

Now multiply by p – 1 to obtain the congruence

(p – 1 ) ! ≡ p – 1 ≡ –1 (mod p).

as was to be proved.

Example: A concrete example should help to clarify the proof Wilson’s theorem. Specifically, let us take p = 13. It is possible to divide the integers 2, 3, …, 11into (p – 3) / 2 = 5 pairs, each product of which is congruent to 1 modulo13. To write this congruences out explicitly:

2 . 3 ≡ 1 (mod 13)

3 . 9 ≡ 1 (mod 13)

  1. 10 ≡ 1 (mod 13)
  2. 8 ≡ 1 (mod 13)

6 . 11 ≡ 1 (mod 13)

Multiplying these congruences gives the result

11 ! = (2.7) (3.9)(4.10)(5.8)(6.11) ≡ 1 (mod 13)

and so

12 ! ≡ 12 ≡ – 1 (mod 13)

Thus, (p – 1 ) ! ≡ – (mod p), with p = 13.

 

Converse of Wilson’s theorem: If (p – 1)! + 1 ≡ 0, then p is prime.

Proof: Suppose that p is not prime. Then p is composite and so there exist a divisor d where 1 < d < p. Furthermore since d is a factor of 1.2.3…(p – 1), so we can write

(p – 1) ! ≡ 0 (mod d)

(p – 1) ! + 1 ≢ 0 (mod d)

⇒ (p – 1) ! + 1 ≢ 0 (mod p)

This is a contradiction of the converse statement.

It follows that p must be a prime. (Proved)

Check Also

Application of Euclidian’s algorithm in Diophantine equation

Problem-1: Which of the following Diophantine equations cannot be solved –   a) 6x + ...

Leave a Reply

Your email address will not be published. Required fields are marked *