mersenneforum.org Primitive Root of Mersenne Numbers
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2016-04-18, 15:11 #1 PawnProver44     "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.
 2016-04-18, 16:10 #2 paulunderwood     Sep 2002 Database er0rr 3·11·107 Posts Code: znorder(Mod(3,2^13-1)) 910
 2016-04-18, 18:12 #3 PawnProver44     "NOT A TROLL" Mar 2016 California C516 Posts Okay so 3 is a cubic residue (mod 2^13-1)... 1807^3 = 3 (mod 8191) I've proved 3 is a quadratic nonresidue of any greater Mersenne Prime.
2016-04-18, 19:45   #4
CRGreathouse

Aug 2006

3·1,987 Posts

Quote:
 Originally Posted by PawnProver44 Okay so 3 is a cubic residue (mod 2^13-1)... 1807^3 = 3 (mod 8191) I've proved 3 is a quadratic nonresidue of any greater Mersenne Prime.
I can only assume this is trolling -- it's pretty easy to find counterexamples. For example:
$610184401^3 \equiv 3\pmod{2^{31}-1}$

 2016-04-18, 21:21 #5 JeppeSN     "Jeppe" Jan 2016 Denmark 101001002 Posts For any odd $$p$$, the number $$M+1=2^p$$ is congruent to 8 modulo 12. So the Mersenne number $$M=2^p-1$$ 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 non-residue modulo a Mersenne prime $$M$$ (other than $$M=3$$). So the troll got one claim right (3 is a quadratic non-residue). However, the stuff about 3 being a primitive root is incorrect. /JeppeSN Last fiddled with by JeppeSN on 2016-04-18 at 21:29
 2016-04-18, 21:53 #6 JeppeSN     "Jeppe" Jan 2016 Denmark 22·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
2016-04-18, 22:18   #7
PawnProver44

"NOT A TROLL"
Mar 2016
California

197 Posts

Quote:
 Originally Posted by JeppeSN 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
Thanks so much for that link. I have a new claim now that if 3 is a primitive root (mod p) and 2^p-1 is prime, then 3 is also a primitive root (mod 2^p-1). No proof for sure but I see that when 2^p-1 is prime, and 3 is not a primitive root (mod p), 3 is also not a primitive root (2^p-1). Now this claim should be proven somehow.

2016-04-18, 23:49   #8
PawnProver44

"NOT A TROLL"
Mar 2016
California

110001012 Posts

Quote:
 Originally Posted by PawnProver44 Thanks so much for that link. I have a new claim now that if 3 is a primitive root (mod p) and 2^p-1 is prime, then 3 is also a primitive root (mod 2^p-1). No proof for sure but I see that when 2^p-1 is prime, and 3 is not a primitive root (mod p), 3 is also not a primitive root (2^p-1). Now this claim should be proven somehow.
(Sorry guys I was wrong)

 Similar Threads Thread Thread Starter Forum Replies Last Post Fusion_power Math 29 2010-10-14 17:05 __HRB__ Math 0 2009-07-10 00:41 T.Rex Math 4 2005-05-07 08:25 juergen Math 12 2005-03-09 08:18 juergen Programming 9 2005-03-08 03:51

All times are UTC. The time now is 21:52.

Tue Jan 19 21:52:06 UTC 2021 up 47 days, 18:03, 0 users, load averages: 1.65, 1.45, 1.61