 mersenneforum.org > Math Mersenne theorems question
 Register FAQ Search Today's Posts Mark Forums Read  2007-10-17, 02:20 #1 ShiningArcanine   Dec 2005 10111002 Posts Mersenne theorems question Are there any theorems that restrict what exponents mersenne prime numbers can have besides the following two?If 2^p - 1 is prime, then p is prime If p is prime, p mod 4 = 3 and 2p+1 is prime, then 2p+1 is a factor of 2^p - 1   2007-10-17, 02:40 #2 Zeta-Flux   May 2003 30138 Posts I imagine the second property follows directly from quadratic reciprocity. You could probably make a similar statement using rational quartic reciprocity. I'll try to work it out, and post again.   2007-10-17, 04:16 #3 Zeta-Flux   May 2003 7·13·17 Posts Quartic reciprocity won't immediately apply since q=4p+1 is congruent to 5 mod 8 (when p is an odd prime). So q won't even be a quadratic residue. Sextic reciprocity shows that if p is a prime, then q=6p+1 divides 2^p-1 if and only if p==1 mod 4 and q=A^2+27*B^2 for some integers A and B. This is already pretty messy. (But it does show, for example, that p=5 leads to q=31=2^2+27*1^2, and so we know 31|2^5-1.) I imagine that octic reciprocity would give conditions satisfied by the pair p=11 and q=8p+1=89. (One can check that 89|2^11-1.) But these conditions keep getting messier (and harder to check).   2007-10-17, 16:06   #4
R.D. Silverman

Nov 2003

22·5·373 Posts Quote:
 Originally Posted by ShiningArcanine Are there any theorems that restrict what exponents mersenne prime numbers can have besides the following two?If 2^p - 1 is prime, then p is prime If p is prime, p mod 4 = 3 and 2p+1 is prime, then 2p+1 is a factor of 2^p - 1
If p = 3 mod 4, then 2p+1 = 7 mod 8 and hence 2 is a quadratic residue.   2007-10-17, 16:57 #5 ShiningArcanine   Dec 2005 22×23 Posts I am not familiar with quadratic reciprocity and quadratic residues. Would you (plural) elaborate on what they are and why 2 is a quadratic residue? By the way, it might be helpful if you (plural) know that I am an undergraduate student and so far, I have taken Calculus I, Calculus II, Calculus III and Introduction to Linear Alegbra.   2007-10-17, 18:11 #6 Zeta-Flux   May 2003 30138 Posts Since you are an undergraduate, I would recommend that if you want to learn about quadratic residues go ahead and take a class on abstract algebra, and then a basic number theory class. Alternatively, if you are highly motivated, pick up a book on beginning number theory (like Andrew's book "Number Theory" printed by Dover).   2012-04-05, 06:54 #7 tomtom2357   Apr 2012 7 Posts Octic reciprocity Does anyone actually know the conditions for octic reciprocity? I would really like to know what they are.   2012-04-05, 11:21   #8
R.D. Silverman

Nov 2003

22·5·373 Posts Quote:
 Originally Posted by tomtom2357 Does anyone actually know the conditions for octic reciprocity? I would really like to know what they are.
They are going to be complicated. Prof. Ken Williams is the expert.   2012-04-05, 11:45   #9
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts Quote:
 Originally Posted by ShiningArcanine I am not familiar with quadratic reciprocity and quadratic residues. Would you (plural) elaborate on what they are and why 2 is a quadratic residue? By the way, it might be helpful if you (plural) know that I am an undergraduate student and so far, I have taken Calculus I, Calculus II, Calculus III and Introduction to Linear Alegbra.
quadratic residues are based in modular (clock) arithmetic and can be found by
x^2=q mod n   2012-04-05, 15:33   #10
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

838410 Posts Quote:
 Originally Posted by Zeta-Flux Quartic reciprocity won't immediately apply since q=4p+1 is congruent to 5 mod 8 (when p is an odd prime). So q won't even be a quadratic residue. Sextic reciprocity shows that if p is a prime, then q=6p+1 divides 2^p-1 if and only if p==1 mod 4 and q=A^2+27*B^2 for some integers A and B. This is already pretty messy. (But it does show, for example, that p=5 leads to q=31=2^2+27*1^2, and so we know 31|2^5-1.) I imagine that octic reciprocity would give conditions satisfied by the pair p=11 and q=8p+1=89. (One can check that 89|2^11-1.) But these conditions keep getting messier (and harder to check).
I made a script based on what you said and it finds over 5600 exponents under 28 million to eliminate based on that in around .6 seconds. a more thorough look gives over 11000 but that includes things like p=5 which give 2^p-1.

Last fiddled with by science_man_88 on 2012-04-05 at 16:04   2012-04-05, 16:08 #11 ATH Einyen   Dec 2003 Denmark 32·5·71 Posts I believe Prime95 uses that factors 2kp+1 are equal to one of these 16 values mod 120: +-1, +-7, +-17, +-23, +-31, +-41, +-47, +-49 (mod 120) This is more strict than +-1 (mod 8) which leads to 30 values mod 120.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post fivemack Abstract Algebra & Algebraic Number Theory 10 2012-01-22 11:01 firejuggler Miscellaneous Math 60 2011-07-19 14:17 rong123 Marin's Mersenne-aries 7 2007-11-09 00:34 stpascu Factoring 1 2006-10-16 16:31 sghodeif Miscellaneous Math 18 2006-07-13 18:24

All times are UTC. The time now is 12:39.

Sun Nov 28 12:39:13 UTC 2021 up 128 days, 7:08, 0 users, load averages: 0.96, 1.49, 1.41