Missing factors

[henryzz]

can anyone proof that a prime cannot be a factor of 2^n+1

my thinking is that it might be possible to prove that if your have checked until p<n i have certainly never found a case when that is false

the first few primes which seem never to be factors of 2^n+1 are:
7, 23, 31, 47, 71, 79, 89, 91

[bsquared]

Originally Posted by henryzz

can anyone proof that a prime cannot be a factor of 2^n+1

You mean, prove that a particular prime is never a factor of 2^n+1. How far have you checked n for the primes you quote?

[henryzz]

i have checked n<10000 including composite ns
yes that is what i mean

edit:i am about to check higher

[henryzz]

i have now checked n<100k

[vector]

I think that to prove that a particular prime will never divide 2^n+1 you need to show that 2^n+1 mod p never equals 0. Or that 2^n mod p is never equal to p-1. So if p-1 is never generated by base 2 mod p then 2^n+1 is never divisible by p.
To show that an element p-1 is generated to base 2 you have compute the factors of p-1 then use them to compute the orders of base 2 mod p and base p-1 mod p. Then show that order of p-1 completely divides the order of 2 mod p. So if p-1 is generated by the base 2 then this prime will sometimes divide 2^x+1.

[petrw1]

It can easily be shown programatically (but not being a qualified mathematician, not proven mathematically) that if you iteratively look for the first multiple of 7 above each 2^n+1 and the difference between these two numbers you get a continued series of 4, 2, 5, 4, 2, 5, 4 ...

I think this is what vector is trying to tell you in mathematical terms. i.e. 7 can never have a mod of zero with 2^n+1

If you want to continue to do this with computer brute force instead of mathematical theory then for other prime factors rather than checking up to "some really big n" only check until there is a repeated pattern of differences as I have with 7.

[henryzz]

thats a way to prove them but what if the chain is so long it cant be spotted

[vector]

thats a way to prove them but what if the chain is so long it cant be spotted

I answered that already. You just have to check whether p-1 is an element generated by 2^x mod p. Also, since p-1 is a special case of being -1 mod p you don't even have to compute the order of p-1 mod p. Just check if 2 has an odd order mod p. (if it has an odd order then p-1 mod p does not exist and that prime therefore never divides the 2^x+1).

[axn]

Originally Posted by vector

I answered that already. You just have to check whether p-1 is an element generated by 2^x mod p. Also, since p-1 is a special case of being -1 mod p you don't even have to compute the order of p-1 mod p. Just check if 2 has an odd order mod p. (if it has an odd order then p-1 mod p does not exist and that prime therefore never divides the 2^x+1).

The check can be done efficiently without (directly) finding the order. Write p-1 as 2^s*k, where k is odd. Then, compute 2^k (mod p). If this is 1, then the order of 2 is odd, and therefore this p will not divide 2^n+1 series.

EDIT:- Why is a composite (91 = 7*13) in that list in the first post??

[henryzz]

i really dont know why i have a composite in that list
i worked out all those primes in my head and must have made a mistake

i misunderstood your first post vector the only parrt could properly understand was what petrw1 explained

[m_f_h]

Originally Posted by axn1

EDIT:- Why is a composite (91 = 7*13) in that list in the first post??

Well it is not /that/ composite, since it's almost (semi-)prime.

see also:
http://www.research.att.com/~njas/sequences/A014663
or rather
http://www.research.att.com/~njas/sequences/A072936 (includes 2)