20160418, 15:11  #1 
"NOT A TROLL"
Mar 2016
California
197 Posts 
Primitive Root of Mersenne Numbers
Prove 3 is a primitive root mod (a Mersenne Prime > 3). I only know how to show that 3 is a quadratic non residue a Mersenne Number which is that all Mersenne Prime > 3 are congruent to 7 (mod 12), and if p = 5 or 7 (mod 12), then 3 is a quadratic nonresidue to p. Similarly, if p = 1 or 11 (mod 12), then 3 is a quadratic residue to p. I don't know how to complete the last part to prove 3 a primitive root of a Mersenne Prime < 3. It would have to be the case that 3 is an xth power nonresidue to all prime factors x of M(n)1. Thanks to whoever can complete the proof.

20160418, 16:10  #2 
Sep 2002
Database er0rr
3·11·107 Posts 
Code:
znorder(Mod(3,2^131)) 910 
20160418, 18:12  #3 
"NOT A TROLL"
Mar 2016
California
C5_{16} Posts 
Okay so 3 is a cubic residue (mod 2^131)... 1807^3 = 3 (mod 8191)
I've proved 3 is a quadratic nonresidue of any greater Mersenne Prime. 
20160418, 19:45  #4  
Aug 2006
3·1,987 Posts 
Quote:
\[610184401^3 \equiv 3\pmod{2^{31}1}\] 

20160418, 21:21  #5 
"Jeppe"
Jan 2016
Denmark
10100100_{2} Posts 
For any odd \(p\), the number \(M+1=2^p\) is congruent to 8 modulo 12. So the Mersenne number \(M=2^p1\) is 7 modulo 12. So by quadratic reciprocity, when \(M\) is prime, we have \(\left(\frac{3}{M}\right) = 1\) (see Legendre symbol where the formula for the case of 3 is given explicitly). So anyone can agree 3 is a quadratic nonresidue modulo a Mersenne prime \(M\) (other than \(M=3\)).
So the troll got one claim right (3 is a quadratic nonresidue). However, the stuff about 3 being a primitive root is incorrect. /JeppeSN Last fiddled with by JeppeSN on 20160418 at 21:29 
20160418, 21:53  #6 
"Jeppe"
Jan 2016
Denmark
2^{2}·41 Posts 
The subset of \(p\) for which the Original Poster is right, i.e. \(M_p\) is a Mersenne prime of which 3 is a primitive root, is OEIS A219461. Note how, beautifully, that OIES entry has a link back to a mersenneforum.org thread. /JeppeSN

20160418, 22:18  #7  
"NOT A TROLL"
Mar 2016
California
197 Posts 
Quote:


20160418, 23:49  #8  
"NOT A TROLL"
Mar 2016
California
11000101_{2} Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Finding the square root of a large mersenne number  Fusion_power  Math  29  20101014 17:05 
Primitive root question  __HRB__  Math  0  20090710 00:41 
LLT numbers, linkd with Mersenne and Fermat numbers  T.Rex  Math  4  20050507 08:25 
Is 3 always a primitive root for mersenne primes?  juergen  Math  12  20050309 08:18 
Is 3 always a primitive root for mersenne primes?  juergen  Programming  9  20050308 03:51 