20040306, 21:14  #1 
Mar 2004
29 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^x1 for x>2? In other words: If 2^x1 is prime is then Ord 3 (mod 2^x1) always 2^x2 = 2(2^(x1)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 
20050307, 04:15  #2 
Mar 2005
8_{16} Posts 
yes
Actually, it's that 'ord 3 (2^p1) divides 2^p2'. But there's an even better congruence:
3^(2^(p1)) = 3 (mod 2^p1). 
20050307, 06:28  #3  
"Nancy"
Aug 2002
Alexandria
4643_{8} Posts 
Quote:
Alex 

20050307, 10:04  #4 
Mar 2005
8_{16} Posts 
ehh...
Sorry, I meant it like this:
'yes, 2^p2 is always an order of 3 mod 2^p1 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? 
20050307, 10:11  #5 
"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^p2 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^p2 is equal to the order of 3.
Alex 
20050307, 14:56  #6  
"Bob Silverman"
Nov 2003
North of Boston
1D54_{16} Posts 
Quote:
A short search reveals that 3^910 = 1 mod (2^131). Thus, 3 is not primitive. What compels people to make such speculations without even a minimal attempt at some numerical verification? 

20050307, 19:46  #7  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}×1,877 Posts 
Quote:
Enuf said????? 

20050307, 22:23  #8 
"Kyle"
Feb 2005
Somewhere near M52..
917_{10} 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).

20050307, 23:13  #9 
"Phil"
Sep 2002
Tracktown, U.S.A.
10001100000_{2} Posts 
Suppose p is prime. Then the congruence classes 1, 2, 3, ..., p1 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.

20050308, 03:51  #10  
Mar 2005
2^{3} Posts 
misuse of terms?
Quote:
I think I missed the point the original poster was aiming at. My apologies. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Primitive Root of Mersenne Numbers  PawnProver44  Miscellaneous Math  7  20160418 23:49 
Primitive roots for a set of primes  mart_r  Math  0  20130720 12:23 
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 
Is 3 always a primitive root for mersenne primes?  juergen  Math  12  20050309 08:18 