*Originally posted by sarathian*

**Can someone prove why does it happen? I will use the notation
**

n! for the factorial of n.

If p is a prime number, then

it always divides (p - 1)! +1. But for any other (non-prime) number n,

(n - 1) ! + 1 is not necessarily ( rather never) divisible by the first prime which is greater than n.

And of course it is never divisible by n too.

Why?

Let p be a prime. Then Z/pZ is a field, so without zero, Z/pZ is a group under multiplication (ie the numbers 1, 2, ... p-1 all have multiplicative inverses). (p-1)! is the product of all of the elements in this group. It's easy to show that the inverses are unique for any group, and if n^2 = 1 (mod p) for some p, then algebra shows n = +-1 (mod p). Thus 1 and p-1 are self inverse, and for each other a in the group, there exists a unique b such that ab = 1 (mod p). Thus the product cancels everything except p-1, so (p-1)! = p-1 = -1 (mod p), ie p divides (p-1)! + 1.

If for some integer n, n divides (n-1)! + 1, then n does not divide (n-1)!. If some integer m between 1 and n not inclusive divides n, then m divides (n-1)! and m divides (n-1)! + 1, a contradiction. Thus such and m cannot exist, so n is prime. Thus composite n cannot divide (n-1)!.

Suppose n is non-prime and that p is the smallest prime greater than n. Then (p-1)! = -1 (mod p). Now since 2 < n-1 < p-1, (n-1)! divides (p-1)!, so say (p-1)! = k(n-1)!. Then k(n-1)! = -1 (mod p). If p divides (n-1)! + 1, then we have k = (p-1)(p-2)...n = 1 (mod p), a clear contradiction unless n = p.