Re: Prime Numbers

Jeremy Cooper writes:
> I found something interesting that I have not proven, but it has not 
> failed yet:

> The integer N is prime if:

>    2^N - 2
>   ---------
>       N              is an integer.

   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)

    For extra credit, prove your hypothesis. ;-)

-Ray
   

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

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

I goofed, I was informed that my little formula didn't quite work so well.
Partly because my calculator rounded when the numbers got large =(

2^31 for example.

                   _  .  _ ___ _  .  _
===-|)/\\/|V|/\/\ (_)/_\|_|\_/(_)/_\|_| Stop by for an excursion into the-===
===-|)||| | |\/\/  mud.crl.com 8888 (_) Virtual Bay Area!                -===