mersenneforum.org > Math A strange new (?) fact about Mersenne factors
 Register FAQ Search Today's Posts Mark Forums Read

 2006-04-08, 13:00 #1 ChriS   Apr 2006 Aachen, Germany 2·3 Posts 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.
 2006-04-08, 14:46 #2 akruppa     "Nancy" Aug 2002 Alexandria 46438 Posts 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!
2006-04-08, 17:42   #3
ChriS

Apr 2006
Aachen, Germany

68 Posts

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.

2006-04-08, 22:43   #4
akruppa

"Nancy"
Aug 2002
Alexandria

1001101000112 Posts

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

2006-04-08, 23:20   #5
R.D. Silverman

Nov 2003

22·5·373 Posts

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.

2006-04-09, 13:36   #6
ChriS

Apr 2006
Aachen, Germany

68 Posts

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

2006-04-10, 09:32   #7
akruppa

"Nancy"
Aug 2002
Alexandria

2,467 Posts

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

2006-04-10, 11:03   #8
R.D. Silverman

Nov 2003

22·5·373 Posts

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]

2006-04-10, 11:16   #9
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

11,317 Posts

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

2006-04-10, 12:24   #10
R.D. Silverman

Nov 2003

22·5·373 Posts

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.

 2006-04-10, 15:37 #11 Zeta-Flux     May 2003 154710 Posts 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."

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

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

Thu May 26 17:35:49 UTC 2022 up 42 days, 15:37, 3 users, load averages: 1.72, 1.97, 1.82