20070618, 04:54  #1 
"Jason Goatcher"
Mar 2005
3·7·167 Posts 
Are there any Fermat numbers that might be prime?
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? Last fiddled with by jasong on 20070618 at 05:25 
20070618, 05:31  #2 
"Jason Goatcher"
Mar 2005
3507_{10} Posts 
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. 
20070618, 05:37  #3 
"Jason Goatcher"
Mar 2005
6663_{8} Posts 
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). Last fiddled with by jasong on 20070618 at 05:40 
20070618, 05:39  #4  
Jun 2003
2^{2}·397 Posts 
Quote:


20070618, 06:23  #5 
Tribal Bullet
Oct 2004
3,547 Posts 
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 2004era hardware. You just have to do 8 billion of these :)
Last fiddled with by jasonp on 20070618 at 06:27 
20070618, 15:48  #6 
Mar 2007
Estonia
149 Posts 
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) 
20070618, 16:14  #7 
"Phil"
Sep 2002
Tracktown, U.S.A.
1119_{10} Posts 
Here's how Pepin's test works. Take any quadratic nonresidue 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^331)) mod 2^(2^33)+1, a computation which starts with 3 and does 2^331 (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.

20070618, 17:06  #8 
"Jason Goatcher"
Mar 2005
DB3_{16} Posts 
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.

20070618, 17:08  #9 
∂^{2}ω=0
Sep 2002
República de California
11,743 Posts 
As others have noted, direct compositeness test of F_{33} is currently way out of reach, even on fast multiprocessor hardware. Once we can get the periteration 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 infinitelymany 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. 
20070618, 17:25  #10 
P90 years forever!
Aug 2002
Yeehaw, FL
7×31×37 Posts 
Throw the book away.
Last fiddled with by Prime95 on 20070618 at 17:26 
20070618, 18:27  #11 
∂^{2}ω=0
Sep 2002
República de California
11,743 Posts 
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^{n} squarings.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
ecm with Fermat numbers  ET_  FermatSearch  1  20160802 19:40 
P1/P+1 on Fermat numbers  ATH  Operazione Doppi Mersennes  2  20150125 06:27 
LLT numbers, linkd with Mersenne and Fermat numbers  T.Rex  Math  4  20050507 08:25 
Fermat Numbers  devarajkandadai  Math  8  20040727 12:27 
Factoring Fermat Numbers  Axel Fox  Software  14  20030704 18:57 