From: Anonymous <mg5n+ea1e6llvoz70pb6bweqlrmyla4udd80xgn0a0saq03@andrew.cmu.edu>
Date: Tue, 12 Apr 94 20:28:56 PDT
To: mg5n+anz3ajg8o1yxicqzt6v6qgpg3tkhddpqw3jl@andrew.cmu.edu (cypherpunks)
Subject: MATH: number theory
Message-ID: <Added.EheqPim00UdaFkvE5d@andrew.cmu.edu>
MIME-Version: 1.0
Content-Type: text/plain


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