-----BEGIN PGP SIGNED MESSAGE----- All right, more people have joined the number theory fun! Somebody other than myself posted:
Well, there is one prime number test which NEVER fails, and that is that (n-1)!+1 mod n is zero for all primes, and non-zero for all non-primes. ;-)
To which Peter Murphy asks:
Would you be able to show me a reference?
I can, and I'm sure the original poster can as well. Any book on number theory should have Wilson's theorem; the second theorem isn't too difficult to prove. The first part of the above statement is a direct result of Wilson's theorem, which I posted in an earlier statement. A recap: Wilson's theorem: for any prime p, (p-1)! = -1 mod p ==> (p-1)! + 1 = 0 mod p See "Elementary Number Theory and its Applications" page 185. As a consequence of Wilson's theorem: for a composite number n, (n-1)! = 0 mod n, except for n = 4 (for n = 4 you get 2) ==> (n-1)! + 1 != 0 mod n For a proof, see "Number Theory and its History" page 261. Hm. hope nobody is getting confused between the factorial notation and C language "not equals" operator. More extensive bibliographic information is available (authors, publishers, etc.) if you want. -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCVAgUBLatmAIOA7OpLWtYzAQFGLAQAlFv9mBD1+T4S8QB7zb+KZlhUtsIzEFH5 CvNw45V1kzbEMp4ydopbcyI9AmkODMZZdaW+lexUPJANqMCf7irb9bG0Jom//711 mvPEZmyVSMTBz33eAA6RSu+mQaaL7Ek1BE64iDXCJFkSyUy2x18Q9+APQ29AaMpH NG6FIbO/Ex8= =FjqL -----END PGP SIGNATURE-----