Editorial : Wilson's theorem

In number theory, Wilson’s theorem states that a natural number n > 1 is a prime number if and only if

((n-1)!) mod n =(n-1)

That is, it asserts that the factorial (n - 1)! = 1 * 2 * 3 * …*(n - 1) is one less than a multiple of n exactly when n is a prime number.

for example :

for n= 4

(n-1) ! = 6

(n-1) ! mod n =2

for n= 5

(n-1) ! = 24

(n-1) ! mod n = 4

for n=6

(n-1) != 120

(n-1) ! mod n =0

for n=11

(n-1) ! = 3628800

(n-1) ! mod n = 10

for n =12

(n-1)! = 39916800

(n-1) ! mod n = 0

Proof:

It is easy to check the result when n is 2 or 3, so let us assume n > 3. If n is composite, then its positive divisors are among the integers

1, 2, 3, 4, … , n-1

and it is clear that gcd( (n-1)! , n) > 1, so we can not have (n-1)! = -1 (mod n).

However if n is prime, then each of the above integers are relatively prime to n. So for each of these integers a there is another b such that ab = 1 (mod n). It is important to note that this b is unique modulo n, and that since n is prime, a = b if and only if a is 1 or n-1. Now if we omit 1 and n-1, then the others can be grouped into pairs whose product is one showing

2.3.4…(n-2) = 1 (mod n)

(or more simply (n-2)! = 1 (mod n)). Finally, multiply this equality by n-1 to complete the proof.

Note : Wilson theorem holds only for prime numbers .

Problem for practice :: SPOJ DCEPC11B

5 Likes

This is an interesting fact, yet it is only appliable on factorial problems. By the way, can somebody tell me the fastest way to verify wether a number is prime?

1 Like

@k1r4 :

miller rabin test is good, there was a problem based on primality testing.

editorial: http://discuss.codechef.com/questions/9723/witmath-editorial

2 Likes