Wolfram Mathworld  explains:

(p-1)!+1 is a multiple of p, that is (p-1)!=-1 (mod p) if and only if (iff) p is prime.
On the other hand for a composite number n, (n-1)!=0 (mod n) except when n=4.
.....................................................................................................................
   
BUT
Fermat's little theorem is a better way to determine primality since Wilson's theorem involves
factorials which are extremely large for even relatively small values of p.  For example to test
71 for primality we would have to do 70!/71 with 70! being larger than 10^100.

It may be easier to understand the concept in terms of quotients.

Except for n=4, IF n is COMPOSITE then (n-1)! must contain in its list 1*2*3*...*(n-1) a pair of factors of n strictly between 1 and n.  Example:  If n=6 then 5! = 1*2*3*4*5 has  2 and 3 as factors of 6.  Hence if we divide 6 into 5! we get an integer for the quotient. 

On the other hand if p is prime then (n-1)! will have no factor of n except 1.  Hence, the
quotient (n-1)!/n will not be integral.

Hence for any integer n>1 and not equal to 4, n is prime iff (n-1)!/n is not an integer
                                                            and  n is composite iff (n-1)!/n is an integer.
n=4 is a special case since the only factor of 4 strictly between 1 and 4 is 2.  Hence 3!/4 is not
an integer.  Note that 9=3*3 but in the list 1*2*3*4*5*6*7*8 we have two factors of 3, one is 3
itself and the other is a factor of 6.  Hence 8!/9 will be integral; that is, 8!/9 = 2*4*5*2*7*8.

Wiki has a proof for Wilson's Theorem (Google Wilson's Theorem Proof).  To follow it one must know
a good bit of number theory.  I am not a number theorist so it refers to things I am not familiar with.
That's why I look at the problem the way I did in my previous post.  Maybe someone else can explain
the number theory congruence bit for you.

Good luck!

Okay, Wilson's theorem.

Last edited by scientia (2012-12-26 17:00:24)

Last edited by scientia (2012-12-26 20:05:20)

Sorry, I thought you understood group theory.

Right. A corollary of Fermat's little theorem is that if p is a prime and a is an integer coprime with p, then there is an integer b such that ab ≡ 1 (mod p).

Proof: Take b = a^p−2.

Moreover, by the division algorithm, we are always guaranteed to find a unique b in the range 1 ≤ b ≤ p−1 such that a^p−2 ≡ b (mod p).

In the language of group theory, we say that b is a multiplicative inverse of a modulo p. This is the result I was using in my proof.

Yes.

No, all the other numbers are not congrent to 1 mod p. It is the product of them and their inverses (which are distinct from themselves) which are congruent to 1 mod p.

I'll illustrate with a few examples.

Last edited by scientia (2013-01-01 19:54:56)