20100906, 07:47  #1 
Sep 2009
24_{16} Posts 
Factorization on 2^p +1
Hi All,
We know the factors of 2^p 1 are in the form 2kp +1, What about Factors of 2^p +1? Do they have a special form and what is the fastest way to find the factors? Thanx 
20100906, 12:52  #2  
"Bob Silverman"
Nov 2003
North of Boston
1D3A_{16} Posts 
Quote:
question. Noone knows the answer to the second question. You need to learn some number theory. 

20100906, 13:29  #3 
"Forget I exist"
Jul 2009
Dumbassville
10000011010001_{2} Posts 
though I have found 1 exception so far hence my idea is flawed. most have a first prime factor that ends in the same digit for those that end in 7,3,5, and end in 3 for ending in 9.
the first exception is 2^32+1 ends in 7 but the first prime factor Pari finds is 641. 
20100906, 15:14  #6  
"Forget I exist"
Jul 2009
Dumbassville
31·271 Posts 
Quote:
Mat([5, 1]),2 [5, 1; 13, 1],6 [5, 2; 41, 1],10 [5, 1; 29, 1; 113, 1],14 [5, 1; 13, 1; 37, 1; 109, 1],18 [5, 1; 397, 1; 2113, 1],22 [5, 1; 53, 1; 157, 1; 1613, 1],26 [5, 2; 13, 1; 41, 1; 61, 1; 1321, 1],30 [5, 1; 137, 1; 953, 1; 26317, 1],34 [5, 1; 229, 1; 457, 1; 525313, 1],38 [5, 1; 13, 1; 29, 1; 113, 1; 1429, 1; 14449, 1],42 [5, 1; 277, 1; 1013, 1; 1657, 1; 30269, 1],46 [5, 3; 41, 1; 101, 1; 8101, 1; 268501, 1],50 [5, 1; 13, 1; 37, 1; 109, 1; 246241, 1; 279073, 1],54 [5, 1; 107367629, 1; 536903681, 1],58 [5, 1; 5581, 1; 8681, 1; 49477, 1; 384773, 1],62 [5, 1; 13, 1; 397, 1; 2113, 1; 312709, 1; 4327489, 1],66 [5, 2; 29, 1; 41, 1; 113, 1; 7416361, 1; 47392381, 1],70 these are all that I searched that have a factor of 5 and they fit 2 mod 4 a lot also have 3 as a first factor. 

20100906, 16:32  #7  
Jun 2003
2·3·17·53 Posts 
Quote:
Try this: Code:
forprime(p=3,100,print(p " " factor((2^p+1)/3))); 

20100906, 16:37  #8 
Banned
"Luigi"
Aug 2002
Team Italia
29×167 Posts 

20100906, 17:58  #9  
"Bob Silverman"
Nov 2003
North of Boston
16472_{8} Posts 
Quote:
except that 2^p+1, p odd, also admits an algebraic factor. 

20100907, 09:44  #10 
Einyen
Dec 2003
Denmark
2^{2}×7×11^{2} Posts 

20100907, 13:07  #11 
"Gang aft agley"
Sep 2002
2·1,877 Posts 
2^{p}+1 in binary is a number with only two bits set, bit 0 and the most significant bit at bit position p. For odd p, 2^{p}+1 is divisible by 3. Dividing out that 3, what is left in binary has a very simple pattern. Set the least significant two bits to 11 and until bit position p2 is reached, repeat the pattern 10 moving to the left. The first few examples look like this:
Code:
9876543210 (bit positions) (bit positions p2 highlighted) 0000000011 0000001011 0000101011 1010101011 addendum: Without thinking about it much, initially I think that after the 3 is divided out, the product of the remaining factors needs to be 3 mod 8. There can be any number of factors that are 1 mod 8 but the rest of the factors must have a product that is 3 mod 8. I haven't thought about factors that are 5 mod 8 or 1 mod 8 (if any or even if these are allowed) and I haven't done the smart thing of doing actual math but I can see that if all the remaining factors that aren't 1 mod 8 are 3 mod 8 that would mean that there would need to be an odd number of factors that are 3 mod 8. Last fiddled with by only_human on 20100907 at 13:42 Reason: added addendum 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factorization of RSA180  Robert Holmes  Factoring  19  20101108 18:46 
Factorization of 7,254+  dleclair  NFSNET Discussion  1  20060321 05:11 
Factorization of 11,212+  Wacky  NFSNET Discussion  1  20060320 23:43 
Factorization of 5,307  Jeff Gilchrist  NFSNET Discussion  7  20050223 19:46 
Factorization of M(738)  McBryce  Factoring  2  20030919 19:32 