20201225, 15:21  #1 
"Matthew Anderson"
Dec 2010
Oregon, USA
661 Posts 
possible overlapping Fermat factor ranges
A Fermat number is F(m) = 2^(2^m) + 1.
It has been shown that any factor of a Fermat number has the form k*2^n + 1. with n greater than or equal to m+2 This information is at fermatsearch.org. if k is not odd then we have an equivalent representation since 2*k*2^c + 1 = k*2^(c+1) + 1 I assume that mmff and other Fermat search programs only search for odd k because the even cases will be searched in increased exponent Also, in the log of known Fermat factors, http://www.prothsearch.com/fermat.html All the k values are odd. Regards, Matt 
20201225, 16:04  #2  
"Mark"
Apr 2003
Between here and the
2^{2}×7×223 Posts 
Quote:
Last fiddled with by rogue on 20201225 at 16:04 

20210105, 09:28  #3 
Romulan Interpreter
Jun 2011
Thailand
2^{3}×19×61 Posts 
If you think about how modular exponentiation works (square and shift), then you will see why even k's are not needed. To test if some q=k*2^n+1 divides some Fm, you start with 2, and square mod q. If you get 1, then q divides F1. If not, you square again, and if 1, then q divides F2. If not, you square again, and if 1, then q divides F3. If not, you square again, and if 1, then q divides F4. If not, you square again, and if 1, then q divides F5.
Now you see why even k are not relevant? Say I want to see if q=296*2^13+1 divides F11 (n has to be at least m+2 from a well known theorem). Repeating the above square+mod nine times, you get that this q divides F9 and you stop. Because two Fermat numbers can't share a factor. Exactly the same result you will get if you try to test if q=37*2^16+1 divides F14  you will run into "q divides F9" and stop after 9 steps (this is the same q). Last fiddled with by LaurV on 20210105 at 09:30 
20210105, 14:34  #4  
"Gary"
Aug 2015
Texas
2×31 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
GIMPS' second Fermat factor!  rajula  Factoring  103  20190312 04:02 
GIMPS' first Fermat factor!  Prime95  Factoring  72  20140607 09:41 
New Fermat factor found!  ET_  Factoring  5  20110113 11:40 
New Fermat factor!  ET_  Factoring  21  20100315 21:02 
New Fermat factor!  ET_  Factoring  42  20081201 12:50 