[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

MATH: number theory

-----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-----