mersenneforum.org > Math Are there any Fermat numbers that might be prime?
 Register FAQ Search Today's Posts Mark Forums Read

 2007-06-18, 04:54 #1 jasong     "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 2007-06-18 at 05:25
 2007-06-18, 05:31 #2 jasong     "Jason Goatcher" Mar 2005 3×7×167 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.
 2007-06-18, 05:37 #3 jasong     "Jason Goatcher" Mar 2005 3·7·167 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 2007-06-18 at 05:40
2007-06-18, 05:39   #4
Citrix

Jun 2003

110010001012 Posts

Quote:
 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...

2007-06-18, 06:23   #5
jasonp
Tribal Bullet

Oct 2004

32·5·79 Posts

Quote:
 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 :)

Last fiddled with by jasonp on 2007-06-18 at 06:27

 2007-06-18, 15:48 #6 kuratkull     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)
 2007-06-18, 16:14 #7 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 21408 Posts 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.
 2007-06-18, 17:06 #8 jasong     "Jason Goatcher" Mar 2005 3·7·167 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.
 2007-06-18, 17:08 #9 ewmayer ∂2ω=0     Sep 2002 República de California 5·2,351 Posts As others have noted, direct compositeness test of F33 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.
2007-06-18, 17:25   #10
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

41×199 Posts

Quote:
 Originally Posted by jasong According to the book 2^2^n+1 requires n squarings.
Throw the book away.

Last fiddled with by Prime95 on 2007-06-18 at 17:26

2007-06-18, 18:27   #11
ewmayer
2ω=0

Sep 2002
República de California

5·2,351 Posts

Quote:
 Originally Posted by Prime95 Throw the book away.
No, the book is correct, 22[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 2n squarings.

 Similar Threads Thread Thread Starter Forum Replies Last Post ET_ FermatSearch 1 2016-08-02 19:40 ATH Operazione Doppi Mersennes 2 2015-01-25 06:27 T.Rex Math 4 2005-05-07 08:25 devarajkandadai Math 8 2004-07-27 12:27 Axel Fox Software 14 2003-07-04 18:57

All times are UTC. The time now is 22:49.

Tue Jan 31 22:49:09 UTC 2023 up 166 days, 20:17, 0 users, load averages: 0.90, 0.94, 0.95