Are there any Fermat numbers that might be prime?

[jasong]

First, let me say, that while I know little about number theory, I'm confident in my ability to notice seemingly odd facts, and therefore be able to ask good questions.

I've been reading in a number theory book I have(made for high school students) about Fermat numbers. In it, it states a method where, for any number 2^2^n+1, it's possible to determine, with n squarings, whether or not it's definitely composite. If anyone wishes I could attempt to post it here(I might make an error, since I don't totally understand the method), but what I was wondering is if anyone has made a program to go through the numbers to check for absolutely certain compositeness. And if so, how far have they gotten?

[jasong]

For those who have been tracking all the changes I've made to the previous post, yes, I am a VERY impulsive person.

Here's the thing: I have an external hard drive with 160GB when it's totally empty. If my calculations are correct(I hope they are), I can handle the math for testing all the Fermat numbers for absolute compositeness up to F40(2^2^40+1). If anyone wants to help me attempt to do any of these numbers(in Linux, it has be done using my Linux box. I'm not going to chance screwing up my Windows box) you can PM me.

[jasong]

For those of you who are interested, here's how the math works for what I want to attempt:

You have a number F(n)=2^2^n+1. You take a number a,(say, a=3)

If F(n) is prime than 3^2^n is congruent to 1 (mod F(n))

I just realized I need to refigure the maximum F(n). Be back in about 15 minutes.

Edit: I think the maximum Fermat number I can handle is F(39).

[Citrix]

Originally Posted by jasong

First, let me say, that while I know little about number theory, I'm confident in my ability to notice seemingly odd facts, and therefore be able to ask good questions.

I've been reading in a number theory book I have(made for high school students) about Fermat numbers. In it, it states a method where, for any number 2^2^n+1, it's possible to determine, with n squarings, whether or not it's definitely composite. If anyone wishes I could attempt to post it here(I might make an error, since I don't totally understand the method), but what I was wondering is if anyone has made a program to go through the numbers to check for absolutely certain compositeness. And if so, how far have they gotten?

I think the book says 2^n squarings...

[jasonp]

Originally Posted by Citrix

I think the book says 2^n squarings...

Yes, Pepin's test requires that many squarings. The smallest Fermat number of unknown character is F33, and a squaring modulo this number requires 1GB of memory and just over 60 seconds on 2004-era hardware. You just have to do 8 billion of these :)

[kuratkull]

This topic seems really interesting, but I don't really grasp the context, anyone care to explain it in a bit simpler terms? :)

PS!: Not a native english speaker, but understand math terms RATHER well(thanks to mersenneforum.org :D)

[philmoore]

Here's how Pepin's test works. Take any quadratic non-residue of a Fermat number, 3 works as well as any other. If we want to test that 2^(2^33)+1 is prime or composite, for example, we simply have to compute 3^(2^(2^33-1)) mod 2^(2^33)+1, a computation which starts with 3 and does 2^33-1 (or 8,589,934,591) squarings mod 2^(2^33)+1. If the result is -1, the Fermat number is prime, otherwise it is composite.

[jasong]

According to the book 2^2^n+1 requires n squarings. So, not many squarings, but the length of the numbers involved doubles each time.

[ewmayer]

As others have noted, direct compositeness test of F₃₃ is currently way out of reach, even on fast multiprocessor hardware. Once we can get the per-iteration time down into the 0.01 second range, we can contemplate such a computation. Perhaps in a decade or so.

As far as the thread title goes, any of the infinitely-many remaining "status unknown" Fermat numbers *might* be prime, but based on the data and some plausible heuristics based on the special form of the factors of such numbers and the sparseness of the candidates (compared e.g. to Mersenne numbers), the odds of this sequence yielding any more primes than the original "gang of five" are extremely small.

[Prime95]

Originally Posted by jasong

According to the book 2^2^n+1 requires n squarings.

Throw the book away.

[ewmayer]

Originally Posted by Prime95

Throw the book away.

No, the book is correct, 2^2[sup]n[/sup] needs n squarings, but that's just the Fermat number *itself* - for Pepin's test we need to raise some number (typically 3, as it's the smallest eligible candidate) to that power, which needs 2ⁿ squarings.