mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-12-07, 16:28   #1
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

166416 Posts
Default 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
henryzz is offline   Reply With Quote
Old 2007-12-07, 16:55   #2
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×17×97 Posts
Default

Quote:
Originally Posted by henryzz View Post
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
bsquared is offline   Reply With Quote
Old 2007-12-07, 17:13   #3
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22·1,433 Posts
Default

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
henryzz is offline   Reply With Quote
Old 2007-12-07, 17:37   #4
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22×1,433 Posts
Default

i have now checked n<100k

Last fiddled with by henryzz on 2007-12-07 at 17:49
henryzz is offline   Reply With Quote
Old 2007-12-07, 18:18   #5
vector
 
vector's Avatar
 
Nov 2007
home

52 Posts
Default

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.
vector is offline   Reply With Quote
Old 2007-12-07, 18:41   #6
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

105138 Posts
Default

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
petrw1 is online now   Reply With Quote
Old 2007-12-07, 21:52   #7
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22·1,433 Posts
Default

thats a way to prove them but what if the chain is so long it cant be spotted
henryzz is offline   Reply With Quote
Old 2007-12-07, 22:35   #8
vector
 
vector's Avatar
 
Nov 2007
home

318 Posts
Default

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).
vector is offline   Reply With Quote
Old 2007-12-08, 00:28   #9
axn
 
axn's Avatar
 
Jun 2003

22·32·131 Posts
Default

Quote:
Originally Posted by vector View Post
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
axn is online now   Reply With Quote
Old 2007-12-08, 10:06   #10
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22·1,433 Posts
Default

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
henryzz is offline   Reply With Quote
Old 2007-12-08, 12:45   #11
m_f_h
 
m_f_h's Avatar
 
Feb 2007

1101100002 Posts
Default

Quote:
Originally Posted by axn1 View Post
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)

Last fiddled with by m_f_h on 2007-12-08 at 12:51
m_f_h is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Any answers on missing factors? schickel Aliquot Sequences 8 2011-11-29 12:24
Missing factors at the 'Known Factors' page MatWur-S530113 PrimeNet 11 2009-01-21 19:08
NewPGen missing factors? lavalamp Software 6 2009-01-14 13:46
Dumb question about missing srsieve factors robo_mojo Riesel Prime Search 4 2008-04-22 04:37
missing? tha Data 6 2003-09-14 21:36

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

Wed Oct 28 03:52:39 UTC 2020 up 48 days, 1:03, 2 users, load averages: 1.17, 1.57, 1.70

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.