mersenneforum.org > Math Missing factors
 Register FAQ Search Today's Posts Mark Forums Read

 2007-12-07, 16:28 #1 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 11×17×31 Posts Missing factors 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
2007-12-07, 16:55   #2
bsquared

"Ben"
Feb 2007

64438 Posts

Quote:
 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?

Last fiddled with by bsquared on 2007-12-07 at 16:55

 2007-12-07, 17:13 #3 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 16A516 Posts i have checked n<10000 including composite ns yes that is what i mean edit:i am about to check higher Last fiddled with by henryzz on 2007-12-07 at 17:14
 2007-12-07, 17:37 #4 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 11×17×31 Posts i have now checked n<100k Last fiddled with by henryzz on 2007-12-07 at 17:49
 2007-12-07, 18:18 #5 vector     Nov 2007 home 52 Posts 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.
 2007-12-07, 18:41 #6 petrw1 1976 Toyota Corona years forever!     "Wayne" Nov 2006 Saskatchewan, Canada 13×349 Posts 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. Last fiddled with by petrw1 on 2007-12-07 at 18:41
 2007-12-07, 21:52 #7 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 11·17·31 Posts thats a way to prove them but what if the chain is so long it cant be spotted
2007-12-07, 22:35   #8
vector

Nov 2007
home

52 Posts

Quote:
 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).

2007-12-08, 00:28   #9
axn

Jun 2003

2·52·97 Posts

Quote:
 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??

Last fiddled with by axn on 2007-12-08 at 00:33

 2007-12-08, 10:06 #10 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 11·17·31 Posts 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
2007-12-08, 12:45   #11
m_f_h

Feb 2007

24·33 Posts

Quote:
 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.

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

Last fiddled with by m_f_h on 2007-12-08 at 12:51

 Similar Threads Thread Thread Starter Forum Replies Last Post schickel Aliquot Sequences 8 2011-11-29 12:24 MatWur-S530113 PrimeNet 11 2009-01-21 19:08 lavalamp Software 6 2009-01-14 13:46 robo_mojo Riesel Prime Search 4 2008-04-22 04:37 tha Data 6 2003-09-14 21:36

All times are UTC. The time now is 06:22.

Thu Jan 28 06:22:46 UTC 2021 up 56 days, 2:34, 0 users, load averages: 2.28, 2.66, 2.63