mersenneforum.org > Math Factorization on 2^p +1
 Register FAQ Search Today's Posts Mark Forums Read

 2010-09-06, 07:47 #1 kurtulmehtap   Sep 2009 3610 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
2010-09-06, 12:52   #2
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by kurtulmehtap 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
Any decent book on elementary number theory will answer the first
question.

Noone knows the answer to the second question.

You need to learn some number theory.

 2010-09-06, 13:29 #3 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26×131 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.
 2010-09-06, 14:01 #4 kar_bon     Mar 2006 Germany 24·3·61 Posts Your 'rule' for exceptions can occur for N=2^n+1 for n == 0 MOD 16. See here for n=1...200. The exceptions are for n=32, 48, 96, 112, 144, 160, 192.
 2010-09-06, 14:06 #5 Mini-Geek Account Deleted     "Tim Sorbera" Aug 2006 San Antonio, TX USA 2×5×7×61 Posts I don't know for sure that it's true, but I think factors q of 2^p+1 must be: q=2kp+1, and q=1 or 3 mod 8 This is from looking at factors of 2^p+1 at the Factor DB.
2010-09-06, 15:14   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts

Quote:
 Originally Posted by Mini-Geek I don't know for sure that it's true, but I think factors q of 2^p+1 must be: q=2kp+1, and q=1 or 3 mod 8 This is from looking at factors of 2^p+1 at the Factor DB.
then how is 5 a factor for like 25% of them ?

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.

2010-09-06, 16:32   #7
axn

Jun 2003

121248 Posts

Quote:
 Originally Posted by science_man_88 then how is 5 a factor for like 25% of them ? 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.
2^p+1 for prime p. 3 is always a factor for them. Google "Wagstaff primes"

Try this:
Code:
forprime(p=3,100,print(p " " factor((2^p+1)/3)));

2010-09-06, 16:37   #8
ET_
Banned

"Luigi"
Aug 2002
Team Italia

2·2,417 Posts

Quote:
 Originally Posted by axn 2^p+1 for prime p. 3 is always a factor for them. Google "Wagstaff primes" Try this: Code: forprime(p=3,100,print(p " " factor((2^p+1)/3)));
not for p=2...

Luigi

2010-09-06, 17:58   #9
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by Mini-Geek I don't know for sure that it's true, but I think factors q of 2^p+1 must be: q=2kp+1, and q=1 or 3 mod 8 This is from looking at factors of 2^p+1 at the Factor DB.
The proof for 2^p+1, p prime is essentially the same as for 2^p-1,
except that 2^p+1, p odd, also admits an algebraic factor.

 2010-09-07, 09:44 #10 ATH Einyen     Dec 2003 Denmark 2×1,601 Posts
 2010-09-07, 13:07 #11 only_human     "Gang aft agley" Sep 2002 2·1,877 Posts 2p+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, 2p+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 p-2 is reached, repeat the pattern 10 moving to the left. The first few examples look like this: Code: 9876543210 (bit positions) (bit positions p-2 highlighted) 0000000011 0000001011 0000101011 1010101011 As can easily be seen, this has a simple pattern. To be a bit more comfortable with this, you can notice that once this pattern is shifted left one position and added to the original pattern (this is multiplying by 3), all but the least significant bit are carried out (placing a bit in bit position p; as is needed for 2p+1). This is pedantic and pattern obsessive, but by looking at the pattern, it is obvious that all the values in the code block above are 3 mod 8. 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 2010-09-07 at 13:42 Reason: added addendum

 Similar Threads Thread Thread Starter Forum Replies Last Post Robert Holmes Factoring 19 2010-11-08 18:46 dleclair NFSNET Discussion 1 2006-03-21 05:11 Wacky NFSNET Discussion 1 2006-03-20 23:43 Jeff Gilchrist NFSNET Discussion 7 2005-02-23 19:46 McBryce Factoring 2 2003-09-19 19:32

All times are UTC. The time now is 03:45.

Wed Dec 8 03:45:51 UTC 2021 up 137 days, 22:14, 1 user, load averages: 1.31, 1.13, 1.17