1994-04-13 - MATH: number theory

Header Data

From: Anonymous <mg5n+ea1e6llvoz70pb6bweqlrmyla4udd80xgn0a0saq03@andrew.cmu.edu>
To: mg5n+anz3ajg8o1yxicqzt6v6qgpg3tkhddpqw3jl@andrew.cmu.edu (cypherpunks)
Message Hash: 14972f57b8e0ab649166706654f95c7965330df5ca2df8d16ae0092f4e148128
Message ID: <Added.EheqPim00UdaFkvE5d@andrew.cmu.edu>
Reply To: N/A
UTC Datetime: 1994-04-13 03:28:56 UTC
Raw Date: Tue, 12 Apr 94 20:28:56 PDT

Raw message

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


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.

Version: 2.3a