mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2016-04-18, 15:11   #1
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

197 Posts
Post 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.
PawnProver44 is offline   Reply With Quote
Old 2016-04-18, 16:10   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×32×11×19 Posts
Default



Code:
znorder(Mod(3,2^13-1))
910
paulunderwood is offline   Reply With Quote
Old 2016-04-18, 18:12   #3
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

197 Posts
Post

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.
PawnProver44 is offline   Reply With Quote
Old 2016-04-18, 19:45   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

175B16 Posts
Default

Quote:
Originally Posted by PawnProver44 View Post
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}\]
CRGreathouse is offline   Reply With Quote
Old 2016-04-18, 21:21   #5
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

101010002 Posts
Default

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
JeppeSN is offline   Reply With Quote
Old 2016-04-18, 21:53   #6
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

23×3×7 Posts
Default

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
JeppeSN is offline   Reply With Quote
Old 2016-04-18, 22:18   #7
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

197 Posts
Post

Quote:
Originally Posted by JeppeSN View Post
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.
PawnProver44 is offline   Reply With Quote
Old 2016-04-18, 23:49   #8
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

110001012 Posts
Post

Quote:
Originally Posted by PawnProver44 View Post
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)
PawnProver44 is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 18:55.


Tue Aug 3 18:55:47 UTC 2021 up 11 days, 13:24, 1 user, load averages: 4.41, 4.39, 3.97

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.