20071207, 16:28  #1 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2^{3}×719 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<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 
20071207, 16:55  #2 
"Ben"
Feb 2007
3,347 Posts 
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 20071207 at 16:55 
20071207, 17:13  #3 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2^{3}·719 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 20071207 at 17:14 
20071207, 17:37  #4 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2^{3}×719 Posts 
i have now checked n<100k
Last fiddled with by henryzz on 20071207 at 17:49 
20071207, 18:18  #5 
Nov 2007
home
5^{2} 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 p1. So if p1 is never generated by base 2 mod p then 2^n+1 is never divisible by p.
To show that an element p1 is generated to base 2 you have compute the factors of p1 then use them to compute the orders of base 2 mod p and base p1 mod p. Then show that order of p1 completely divides the order of 2 mod p. So if p1 is generated by the base 2 then this prime will sometimes divide 2^x+1. 
20071207, 18:41  #6 
1976 Toyota Corona years forever!
"Wayne"
Nov 2006
Saskatchewan, Canada
10567_{8} 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 20071207 at 18:41 
20071207, 21:52  #7 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
13170_{8} Posts 
thats a way to prove them but what if the chain is so long it cant be spotted

20071207, 22:35  #8  
Nov 2007
home
5^{2} Posts 
Quote:


20071208, 00:28  #9  
Jun 2003
4790_{10} Posts 
Quote:
EDIT: Why is a composite (91 = 7*13) in that list in the first post?? Last fiddled with by axn on 20071208 at 00:33 

20071208, 10:06  #10 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2^{3}·719 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 
20071208, 12:45  #11  
Feb 2007
2^{4}×3^{3} Posts 
Quote:
see also: 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 20071208 at 12:51 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Any answers on missing factors?  schickel  Aliquot Sequences  8  20111129 12:24 
Missing factors at the 'Known Factors' page  MatWurS530113  PrimeNet  11  20090121 19:08 
NewPGen missing factors?  lavalamp  Software  6  20090114 13:46 
Dumb question about missing srsieve factors  robo_mojo  Riesel Prime Search  4  20080422 04:37 
missing?  tha  Data  6  20030914 21:36 