Thread: Eureka!

Okay, so I am absolutely obsessed with prime numbers, and for the past two years or so I've experimented with various schemes for detecting them (much to no avail). Well, last night I fell asleep with my mind complete fixated on the problem (once again!). Suddenly, in the midst of a dream, an equation came to mind, and I instinctively plugged a few numbers into it. Each and every one I tried worked, and I became so excited that I woke up in a cold sweat! I brewed some coffee and got to work on a simple test program. Running the program, my heart sunk as it started spitting out values that failed the test. Damn! But then, as I looked closer at the numbers, I noticed something that caused my hair to literally stand up on end - 561, 1105, 1729, 2465, 2821...these were the first five Carmichael numbers! In other words, my equation was essentially equivalent to Fermat's primality test to every base!!!

Here is the theorem, in detail:

IFF gcd(s(N, N - 1) mod s(N, 1), N) = 1 then N is either a prime or a Carmichael number, where s(N, E) is the sum of powers (eg: 1^E + 2^E ... + N^E).

From a practical viewpoint, I do realize that it may be inefficient to compute (although I haven't yet confirmed that), but nonetheless it does amount to a much more concise generalization of Fermat's Little Theorem.

Originally Posted by Epy

N - 1 is way too big of an exponent, I don't think that'd be good for any range of numbers...

Code:

MATLAB:
sp=@ (n,e) sum((1:n).^e);

octave-3.2.4.exe:13> sp(100,99)
ans =  1.5812e+198

Actually, you can use modular exponentiation to keep the result down to a manageable size (moreover, the modulus can be applied to the accumulated sum as well). The real problem is calculating the "sum of powers" efficiently. The technique that I used simply cycles through 1 -> N, which is slow, to say the least (even trial division would be a faster primality test!), but I'm investigating the possibility that there even exists a method to that efficiently. So for now, the equation has only theoretical significance, in that it compactly describes Fermat's Little Theorem to all number bases (comparably, Wilson's theorem is completely impractical, but nonetheless, it's the most concise definition of primality, to date).

Originally Posted by Epy

Interesting. That still seems pretty intensive. I guess my question is, what is the advantage of your theorem over the other existing pseudoprime theorems?

Essentially, it just amounts to a much stronger statement of the domain of N^E-1 mod E for any given N, whereas Fermat's Little Theorem requires much more complex definitions.

Can my conjecture be used to construct a better Fermat primality test? Maybe, maybe not, but that's really beside the point. There are numerous tests that are much more accurate than Fermat's (Miller-Rabin, Solovay-Strassen, etc), and again, computing my equation may well be too expensive to be practical. The important point is that the generalization is (1) compact, and thus (2) may be helpful in generalizing existing mathematical principles, or in constructing completely new theories. At any rate, it's theoretical importance remains to be seen. I've already notified members of the math community, including a few friends of mine, but considering that my conjecture is just a few days old at this point, it could be a quite a while before any useful results arise from it.*


*Okay, just for the record, it took less than 48 hours (see here).