Factorization on 2^p +1

[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

[R.D. Silverman]

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.

[science_man_88]

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.

[kar_bon]

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.

[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.

[science_man_88]

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.

[axn]

Originally Posted by science_man_88

then how is 5 a factor for like 25% of them ?

<snip>
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:

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

[ET_]

Originally Posted by axn

2^p+1 for prime p. 3 is always a factor for them. Google "Wagstaff primes"

Try this:

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

not for p=2...

Luigi

[R.D. Silverman]

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.

[ATH]

http://www.mersenneforum.org/showpos...0&postcount=92

[only_human]

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 p-2 is reached, repeat the pattern 10 moving to the left. The first few examples look like this:

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 2^p+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.