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: [URL="http://primes.utm.edu/notes/proofs/MerDiv2.html"]http://primes.utm.edu/notes/proofs/MerDiv2.html[/URL]), 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.

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 [url]http://www.mersenneforum.org/showthread.php?t=5103[/url] where I asked a related question.

Alex

[QUOTE=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 [url]http://www.mersenneforum.org/showthread.php?t=5103[/url] where I asked a related question.

Alex[/QUOTE]

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=akruppa]Let p, q be prime, p≡1 (mod q) and p≡±1 (mod 8), 2k=(p-1)/q.[/QUOTE]

But in the next line, you have them quoted correctly:
[QUOTE=akruppa]q|Mp iff ord_q(2)=p. The subgroup of elements of order p in Z/Zq has p-1 elements.[/QUOTE]

Also, I don't understand this argument:
[QUOTE=akruppa]The elements of order q, with q odd, are also squares...[/QUOTE]

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

Thanks.

[QUOTE=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:
[/QUOTE]

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=ChriS]
Also, I don't understand this argument:

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

Thanks.[/QUOTE]

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

[QUOTE=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 [url]http://www.mersenneforum.org/showthread.php?t=5103[/url] where I asked a related question.

Alex[/QUOTE]

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.

[QUOTE=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[/QUOTE]

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

[QUOTE=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.[/QUOTE]

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

[QUOTE=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[/QUOTE]

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]

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


Paul

[QUOTE=xilman]A possible solution: post her contact details and let others talk to her.


Paul[/QUOTE]

She teaches at Nashua High School, Nashua N.H., USA.
I have no other contact info.

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