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