From: rjc@gnu.ai.mit.edu (Ray)
Date: Mon, 11 Apr 94 19:59:36 PDT
To: cypherpunks@toad.com
Subject: Prime Numbers
Message-ID: <9404120259.AA11138@geech.gnu.ai.mit.edu>
MIME-Version: 1.0
Content-Type: text/plain


Eric Hughes:


> It was first claimed that if (2^n-2)/n was an integer, then n was
> prime.  That's false.  

    I thought he said "if p prime, then p|(2^p-2)" which is why
I stated the converse isn't true.

> then:
> >   This is fermat's little theorem. What you have written basically
> >says 2^N - 2  = 0 (mod N) or 2^(N-1) = 1 (mod N). Note, the converse
> >doesn't apply. If (2^N-2)/N is an integer, N isn't neccessarily
> >prime. For example, take N=561=(3*11*37)
> 
> 561 is the first Carmichael number.  If you replace 2 by any other
> number relatively prime to 561, then the congruence still holds.  (The
> second Carmichael number is 1729, if I remember right.)  It was

   Which is why I chose it. Carmichael numbers are pseudoprime in
any valid base so when coming up with a counterexample to the converse
of fermat's little theorem, just memorize a few Carmichael numbers. The key 
property of them is if n is a Carmichael number and n=p*q*r, then (p-1), 
(q-1), and (r-1) divide (n-1).

   I wonder if Carmichael numbers always have some small factors. If true,
PGP's sieve test probably eliminates the very very rare case that
you actually choose one.

-Ray
-- Ray Cromwell        |    Engineering is the implementation of science;   --
-- rjc@gnu.ai.mit.edu  |       politics is the implementation of faith.     --