20201225, 15:21  #1 
"Matthew Anderson"
Dec 2010
Oregon, USA
1111110000_{2} 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
5×1,307 Posts 
Quote:
Last fiddled with by rogue on 20201225 at 16:04 

20210105, 09:28  #3 
Romulan Interpreter
"name field"
Jun 2011
Thailand
2·3·5·7·47 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 Gostin"
Aug 2015
Texas, USA
67 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 