20060408, 13:00  #1 
Apr 2006
Aachen, Germany
6_{10} 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. 
20060408, 14:46  #2 
"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=(q1)/p. qMp iff ord_q(2)=p. The subgroup of elements of order p in Z/Zq has p1 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 (q1)/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/((q1)/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 20060409 at 04:22 Reason: p,q still fubar! 
20060408, 17:42  #3  
Apr 2006
Aachen, Germany
2·3 Posts 
Quote:
Quote:
Quote:
Quote:
Thanks. 

20060408, 22:43  #4  
"Nancy"
Aug 2002
Alexandria
2467_{10} Posts 
Quote:
Quote:
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 

20060408, 23:20  #5  
"Bob Silverman"
Nov 2003
North of Boston
5^{2}×13×23 Posts 
Quote:
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. 

20060409, 13:36  #6  
Apr 2006
Aachen, Germany
6_{8} Posts 
Quote:
Thanks, Christian 

20060410, 09:32  #7  
"Nancy"
Aug 2002
Alexandria
2467_{10} Posts 
Quote:
Alex 

20060410, 11:03  #8  
"Bob Silverman"
Nov 2003
North of Boston
16463_{8} Posts 
Quote:
every prime, with at most 2 exceptions, was a primitive root i.o. The method extends to showing the same result for subgroups. [my ex would know, but I don't talk to her] 

20060410, 11:16  #9  
Bamboozled!
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across
11,483 Posts 
Quote:
Paul 

20060410, 12:24  #10  
"Bob Silverman"
Nov 2003
North of Boston
5^{2}·13·23 Posts 
Quote:
I have no other contact info. 

20060410, 15:37  #11 
May 2003
11000001011_{2} Posts 
Alex,
The paper in question is called "Artin's conjecture for primitive roots." It is quite fascinating. Basically HeathBrown improves on a previous paper of Gupta and Ram Murty (which said there were finitely many prime counterexamples to Artin's conjecture) by introducing a sieve method to get the number down. The sieve has something to do with the BombieriVinogradov 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 bigO equation. If you are still interested in taking a look at this stuff, I recommend googling "Artin's conjecture" along with "primitive." 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Distribution of Mersenne Factors  tapion64  Miscellaneous Math  21  20140418 21:02 
Known Mersenne factors  CRGreathouse  Math  5  20130614 11:44 
strange factors distribution??  pegaso56  Information & Answers  19  20090629 15:04 
Factors of Mersenne Numbers  asdf  Math  17  20040724 14:00 
Factors of Mersenne numbers ?  Fusion_power  Math  13  20031028 20:52 