A strange new (?) fact about Mersenne factors

ChriS · 2006-04-08, 13:00

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.

akruppa · 2006-04-08, 14:46

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

ChriS · 2006-04-08, 17:42

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.

akruppa · 2006-04-08, 22:43

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

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

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.

ChriS · 2006-04-09, 13:36

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

akruppa · 2006-04-10, 09:32

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

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

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]

xilman · 2006-04-10, 11:16

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

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

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.

Zeta-Flux · 2006-04-10, 15:37

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."

2006-04-08, 13:00	#1
ChriS Apr 2006 Aachen, Germany 6₁₀ 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 2,467 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!

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

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