mersenneforum.org  

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

Reply
 
Thread Tools
Old 2006-04-08, 13:00   #1
ChriS
 
Apr 2006
Aachen, Germany

2×3 Posts
Default A strange new (?) fact about Mersenne factors

I considered prime factors q = 2 k p + 1, q = +/- 1 (mod 8) of Mp, p prime.

The strange thing I found is that for k fixed, about 1/k of all primes q generated this way divide their corresponding Mp. For k = 1 this reflects the fact that every such q divides Mp (for a proof see here: http://primes.utm.edu/notes/proofs/MerDiv2.html), but for bigger k's I have not found any results yet.

Note that for k = 2 (mod 4), no such candidates q exist due to the q = +/- 1 (mod 8) condition.

Up to now I only have statistical evidence for this fact, but I would like to know whether
a) it is well known?
b) if so, one can proove it rigorously?

I also tried to figure out whether (for k = 3) a criterion could be found that states which of the q's divide Mp. I experimented with moduli of p and prime roots, but I couldn't find a hint.
ChriS is offline   Reply With Quote
Old 2006-04-08, 14:46   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25·7·11 Posts
Default

This is well known and easily shown with some elementary group theory.

Let p, q be prime, q≡1 (mod p) and q≡±1 (mod 8), 2k=(q-1)/p.
q|Mp iff ord_q(2)=p. The subgroup of elements of order p in Z/Zq has p-1 elements.

Since q≡±1 (mod 8), 2 is a square in Z/Zq. The elements of order p, with p odd, are also squares and there are a total of (q-1)/2 squares in Z/Zq.

If we assume that 2 behaves randomly wrt the probability of being in a particular subgroup, we would expect that Pr[ord_q(2)=p] is p/((q-1)/2) = 1/k.

Whether or not 2 behaves randomly in this way is unproven, afaik. See http://www.mersenneforum.org/showthread.php?t=5103 where I asked a related question.

Alex

Last fiddled with by akruppa on 2006-04-09 at 04:22 Reason: p,q still fubar!
akruppa is offline   Reply With Quote
Old 2006-04-08, 17:42   #3
ChriS
 
Apr 2006
Aachen, Germany

616 Posts
Default

Quote:
Originally Posted by akruppa
This is well known and a easily shown with some elementary group theory.

Let p, q be prime, p≡1 (mod q) and p≡±1 (mod 8), 2k=(p-1)/q.
q|Mp iff ord_q(2)=p. The subgroup of elements of order p in Z/Zq has p-1 elements.

Since p≡±1 (mod 8), 2 is a square. The elements of order q, with q odd, are also squares and there are (p-1)/2 squares in Z/Zp.

If we assume that 2 behaves randomly wrt the probability of being in a particular subgroup, we would expect that Pr[ord_q(2)=p] is q/((p-1)/2) = 1/k.

Whether or not 2 behaves randomly in this way is unproven, afaik. See http://www.mersenneforum.org/showthread.php?t=5103 where I asked a related question.

Alex
I'm getting confused with the p's and q's in your reply. Here you state p and q the other way I defined them:
Quote:
Originally Posted by akruppa
Let p, q be prime, p≡1 (mod q) and p≡±1 (mod 8), 2k=(p-1)/q.
But in the next line, you have them quoted correctly:
Quote:
Originally Posted by akruppa
q|Mp iff ord_q(2)=p. The subgroup of elements of order p in Z/Zq has p-1 elements.
Also, I don't understand this argument:
Quote:
Originally Posted by akruppa
The elements of order q, with q odd, are also squares...
I'm not an expert in group theory (not even elementary ), so could you explain that in a bit more detail?

Thanks.
ChriS is offline   Reply With Quote
Old 2006-04-08, 22:43   #4
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25·7·11 Posts
Default

Quote:
Originally Posted by ChriS
I'm getting confused with the p's and q's in your reply. Here you state p and q the other way I defined them:
Sorry. I typed that 10 minutes after waking up this morning... I had wondered if it was wise to type math while still half asleep. Obviously not...

Quote:
Originally Posted by ChriS
Also, I don't understand this argument:

I'm not an expert in group theory (not even elementary ), so could you explain that in a bit more detail?

Thanks.
For odd q, the group (Z/Zq)* has even order, namely q-1. So any element of odd order must necessarily be a square in that group.

Sorry, I couldn't explain group theory in a forum, I only know the elementary stuff myself and even that would take far too long to write up. Much better to pick up an introductory text book on algebra. Is there a good text available online somewhere?

Alex
akruppa is offline   Reply With Quote
Old 2006-04-08, 23:20   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1C4016 Posts
Default

Quote:
Originally Posted by akruppa
This is well known and a easily shown with some elementary group theory.

Let p, q be prime, q≡1 (mod p) and q≡±1 (mod 8), 2k=(q-1)/p.
q|Mp iff ord_q(2)=p. The subgroup of elements of order p in Z/Zq has p-1 elements.

Since q≡±1 (mod 8), 2 is a square in Z/Zq. The elements of order p, with p odd, are also squares and there are a total of (p-1)/2 squares in Z/Zp.

If we assume that 2 behaves randomly wrt the probability of being in a particular subgroup, we would expect that Pr[ord_q(2)=p] is p/((q-1)/2) = 1/k.

Whether or not 2 behaves randomly in this way is unproven, afaik. See http://www.mersenneforum.org/showthread.php?t=5103 where I asked a related question.

Alex
Work done by Roger Heath-Brown (very deep analytic number theory)
shows that almost all primes 'behave randomly' in this sense. In fact,
his work shows that there are at most 2 primes that are NOT.
R.D. Silverman is offline   Reply With Quote
Old 2006-04-09, 13:36   #6
ChriS
 
Apr 2006
Aachen, Germany

2·3 Posts
Default

Quote:
Originally Posted by akruppa
Sorry. I typed that 10 minutes after waking up this morning... I had wondered if it was wise to type math while still half asleep. Obviously not...



For odd q, the group (Z/Zq)* has even order, namely q-1. So any element of odd order must necessarily be a square in that group.

Sorry, I couldn't explain group theory in a forum, I only know the elementary stuff myself and even that would take far too long to write up. Much better to pick up an introductory text book on algebra. Is there a good text available online somewhere?

Alex
In lack of a good algebra textbook, I started to experiment with my computer, and I think I understand the argument now. At least, I know now where to look for further details.

Thanks,
Christian
ChriS is offline   Reply With Quote
Old 2006-04-10, 09:32   #7
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25×7×11 Posts
Default

Quote:
Originally Posted by R.D. Silverman
Work done by Roger Heath-Brown (very deep analytic number theory)
shows that almost all primes 'behave randomly' in this sense. In fact,
his work shows that there are at most 2 primes that are NOT.
Thanks for this info. I googled for Roger Heath-Brown but found very little aside from a request for reporting typos in Hardy&Wright and some citations in other papers. Do you happen to have a reference for the work you mentioned? I doubt I'll understand much of it but at least I'd like to have a peek.

Alex
akruppa is offline   Reply With Quote
Old 2006-04-10, 11:03   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by akruppa
Thanks for this info. I googled for Roger Heath-Brown but found very little aside from a request for reporting typos in Hardy&Wright and some citations in other papers. Do you happen to have a reference for the work you mentioned? I doubt I'll understand much of it but at least I'd like to have a peek.

Alex
I don't recall the exact reference. It is a paper that showed that
every prime, with at most 2 exceptions, was a primitive root i.o.
The method extends to showing the same result for sub-groups.

[my ex would know, but I don't talk to her]
R.D. Silverman is offline   Reply With Quote
Old 2006-04-10, 11:16   #9
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

27CF16 Posts
Default

Quote:
Originally Posted by R.D. Silverman
[my ex would know, but I don't talk to her]
A possible solution: post her contact details and let others talk to her.


Paul
xilman is offline   Reply With Quote
Old 2006-04-10, 12:24   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

161008 Posts
Default

Quote:
Originally Posted by xilman
A possible solution: post her contact details and let others talk to her.


Paul
She teaches at Nashua High School, Nashua N.H., USA.
I have no other contact info.
R.D. Silverman is offline   Reply With Quote
Old 2006-04-10, 15:37   #11
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

5F216 Posts
Default

Alex,

The paper in question is called "Artin's conjecture for primitive roots." It is quite fascinating. Basically Heath-Brown improves on a previous paper of Gupta and Ram Murty (which said there were finitely many prime counter-examples to Artin's conjecture) by introducing a sieve method to get the number down. The sieve has something to do with the Bombieri-Vinogradov theorem and such. The reason one ends up with 3 primes, I think, arises from some sort of inability to improve an exponent in a big-O equation.

If you are still interested in taking a look at this stuff, I recommend googling "Artin's conjecture" along with "primitive."
Zeta-Flux is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Distribution of Mersenne Factors tapion64 Miscellaneous Math 21 2014-04-18 21:02
Known Mersenne factors CRGreathouse Math 5 2013-06-14 11:44
strange factors distribution?? pegaso56 Information & Answers 19 2009-06-29 15:04
Factors of Mersenne Numbers asdf Math 17 2004-07-24 14:00
Factors of Mersenne numbers ? Fusion_power Math 13 2003-10-28 20:52

All times are UTC. The time now is 17:20.

Mon Nov 23 17:20:57 UTC 2020 up 74 days, 14:31, 2 users, load averages: 1.89, 1.94, 1.85

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.