mersenneforum.org  

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

Reply
 
Thread Tools
Old 2007-10-17, 02:20   #1
ShiningArcanine
 
ShiningArcanine's Avatar
 
Dec 2005

10111002 Posts
Default 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
ShiningArcanine is offline   Reply With Quote
Old 2007-10-17, 02:40   #2
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

30138 Posts
Default

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.
Zeta-Flux is offline   Reply With Quote
Old 2007-10-17, 04:16   #3
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

7·13·17 Posts
Default

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).
Zeta-Flux is offline   Reply With Quote
Old 2007-10-17, 16:06   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by ShiningArcanine View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2007-10-17, 16:57   #5
ShiningArcanine
 
ShiningArcanine's Avatar
 
Dec 2005

22×23 Posts
Default

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.
ShiningArcanine is offline   Reply With Quote
Old 2007-10-17, 18:11   #6
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

30138 Posts
Default

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).
Zeta-Flux is offline   Reply With Quote
Old 2012-04-05, 06:54   #7
tomtom2357
 
Apr 2012

7 Posts
Default Octic reciprocity

Does anyone actually know the conditions for octic reciprocity? I would really like to know what they are.
tomtom2357 is offline   Reply With Quote
Old 2012-04-05, 11:21   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by tomtom2357 View Post
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.
"Google is my friend".
R.D. Silverman is offline   Reply With Quote
Old 2012-04-05, 11:45   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by ShiningArcanine View Post
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
science_man_88 is offline   Reply With Quote
Old 2012-04-05, 15:33   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by Zeta-Flux View Post
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
science_man_88 is offline   Reply With Quote
Old 2012-04-05, 16:08   #11
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

32·5·71 Posts
Default

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.
ATH is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Theorems about ideals fivemack Abstract Algebra & Algebraic Number Theory 10 2012-01-22 11:01
Mersenne, another question firejuggler Miscellaneous Math 60 2011-07-19 14:17
Question about Mersenne Numbers rong123 Marin's Mersenne-aries 7 2007-11-09 00:34
odd divisors of Mersenne-like, question stpascu Factoring 1 2006-10-16 16:31
new theorems about primes 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.