mersenneforum.org Is 3 always a primitive root for mersenne primes?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2004-03-06, 21:14 #1 juergen   Mar 2004 111012 Posts Is 3 always a primitive root for mersenne primes? Hello, the subject sais it all. Is 3 always a primitive root for primes of the form 2^x-1 for x>2? In other words: If 2^x-1 is prime is then Ord 3 (mod 2^x-1) always 2^x-2 = 2(2^(x-1)-1)? I checked this up to 127, okay thats not a lot, but I guess that this is really right and I wonder if there is already a proof for that. kind regards Jürgen
 2005-03-07, 04:15 #2 abiessu   Mar 2005 23 Posts yes Actually, it's that 'ord 3 (2^p-1) divides 2^p-2'. But there's an even better congruence: 3^(2^(p-1)) = -3 (mod 2^p-1).
2005-03-07, 06:28   #3
akruppa

"Nancy"
Aug 2002
Alexandria

46438 Posts

Quote:
 Originally Posted by abiessu Actually, it's that 'ord 3 (2^p-1) divides 2^p-2'. But there's an even better congruence: 3^(2^(p-1)) = -3 (mod 2^p-1).
The first follows from Lagrange's theorem. The second follows from the fact that 3 is a quadratic non-residue (mod 2^p-1) for Mersenne primes with odd p. Neither answers the original question.

Alex

 2005-03-07, 10:04 #4 abiessu   Mar 2005 816 Posts ehh... Sorry, I meant it like this: 'yes, 2^p-2 is always an order of 3 mod 2^p-1 given the conditions you've described, and it just so happens that...' I got a little carried away, new to the forum and all... But... umm... doesn't that answer the original?
 2005-03-07, 10:11 #5 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts The order of an element a is the smallest positive integer n so that a^n == 1. You showed that 2^p-2 is a multiple of the order of 3 (which is what Lagrange's theorem states, the order of an element divides the order of the group), but not that 2^p-2 is equal to the order of 3. Alex
2005-03-07, 14:56   #6
R.D. Silverman

Nov 2003

164448 Posts

Quote:
 Originally Posted by akruppa The order of an element a is the smallest positive integer n so that a^n == 1. You showed that 2^p-2 is a multiple of the order of 3 (which is what Lagrange's theorem states, the order of an element divides the order of the group), but not that 2^p-2 is equal to the order of 3. Alex
Disproof by counter-example.

A short search reveals that 3^910 = 1 mod (2^13-1).

Thus, 3 is not primitive.

What compels people to make such speculations without even a minimal
attempt at some numerical verification?

2005-03-07, 19:46   #7
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by R.D. Silverman Disproof by counter-example. A short search reveals that 3^910 = 1 mod (2^13-1). Thus, 3 is not primitive. What compels people to make such speculations without even a minimal attempt at some numerical verification?
Another example: Let P = 2^61-1, then 3^( (P-1)/3) = 1 mod P.

Enuf said?????

 2005-03-07, 22:23 #8 Primeinator     "Kyle" Feb 2005 Somewhere near M50..sshh! 2·3·149 Posts Please pardon me, I'm only a sophomore in an american high school. Could someone please explain to me what a primitive root is? (I know what square roots and cubic roots and 4th roots, etc etc are).
 2005-03-07, 23:13 #9 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 2×13×43 Posts Suppose p is prime. Then the congruence classes 1, 2, 3, ..., p-1 form a group under multiplication. (Example: p = 11, then 2*7 = 14 = 3 mod 11.) A primitive root is a congruence class that generates all the other congruence classes when you take its powers. So the consecutive powers of 2 mod 11 are: 2, 4, 8, 5, 10, 9, 7, 3, 6, and 1, so 2 is a primitive root mod 11. On the other hand, the powers of 3 mod 11 are: 3, 9, 3, 4, 1, 3, 9, 3, 4, 1, etc., so 3 is not a primitive root.
2005-03-08, 03:51   #10
abiessu

Mar 2005

810 Posts
mis-use of terms?

Quote:
 Originally Posted by R.D. Silverman Disproof by counter-example. A short search reveals that 3^910 = 1 mod (2^13-1). Thus, 3 is not primitive. What compels people to make such speculations without even a minimal attempt at some numerical verification?
(No, I'm not saying that you mis-used terms.)

I think I missed the point the original poster was aiming at. My apologies.

 Similar Threads Thread Thread Starter Forum Replies Last Post PawnProver44 Miscellaneous Math 7 2016-04-18 23:49 mart_r Math 0 2013-07-20 12:23 Fusion_power Math 29 2010-10-14 17:05 __HRB__ Math 0 2009-07-10 00:41 juergen Math 12 2005-03-09 08:18

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

Sun Jan 24 18:33:42 UTC 2021 up 52 days, 14:45, 0 users, load averages: 2.11, 2.54, 3.19