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! -===
participants (3)
-
hughes＠ah.com -
Jeremy Cooper -
rjc＠gnu.ai.mit.edu