1994-04-11 - Prime Numbers

Header Data

From: hughes@ah.com (Eric Hughes)
To: cypherpunks@toad.com
Message Hash: 12f777e80fcc0a4fd4713411b93eb754adb5efc62f9a69b3b200bfe8fb3a41fa
Message ID: <9404111947.AA20026@ah.com>
Reply To: <9404110253.AA12284@geech.gnu.ai.mit.edu>
UTC Datetime: 1994-04-11 19:57:57 UTC
Raw Date: Mon, 11 Apr 94 12:57:57 PDT

Raw message

From: hughes@ah.com (Eric Hughes)
Date: Mon, 11 Apr 94 12:57:57 PDT
To: cypherpunks@toad.com
Subject: Prime Numbers
In-Reply-To: <9404110253.AA12284@geech.gnu.ai.mit.edu>
Message-ID: <9404111947.AA20026@ah.com>
MIME-Version: 1.0
Content-Type: text/plain


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

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
recently proven that there are infinitely many Carmichael numbers, and
that the density of Carmichael numbers is at least x^c, where c is
about .1.

Eric





Thread