20060514, 14:35  #1 
Feb 2004
France
2×461 Posts 
Conjecture about multiplicative order of 3 modulo a Mersenne prime
In thread LLT DiGraph, maxal had the idea to compute (Mq1)/order(3,Mq) for some values of q, and then I completed up to q=1279.
Then it appears that we have the following conjecture, showing that 3 is a primitive root modulo Mq for a subset of the Mersenne primes. Any idea to prove it or to compute more examples ? Tony Data: Code:
q (Mq1)/order(3,Mq)  3 1 5 1 7 1 13 9 17 1 19 1 31 3 61 9 89 1 107 1 127 3 521 1 607 3 1279 3 Code:
\r cunn2.gp mo3(q) = { M=2^q1; (M1)/znorder(Mod(3,M)) } 
20060514, 19:01  #2 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
For all known prime factors q of M22031, 3 is not a qth power (mod M2203). However, 2^1101+1 is not completely factored, a c217 remains. This would make a pretty attractive target for SNFS.
Alex Code:
? M=2^22031; ? f=[2,3,7,2203,12479,19819,28627,79273,51791041,78138581882953,146264881313513,20837062885084633147,258977744356523549983,301311116540899114446723859201,883533090360873723903538281367,460233616861852066165180033789571,1636198597169607245088331633873083979,711718443060888357455104383759579899185453159253854240850359788937324328008225366876777905349283339583535597500393178373807851032788989008946432082299780350922963303,19755740081951910036006278827509875120092863638283602681]; ? for(i=1,length(f),print(Mod(3,M)^((M1)/f[i])==Mod(1,M))) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Last fiddled with by akruppa on 20060514 at 19:41 
20060515, 01:21  #3  
Nov 2003
2^{2}×5×373 Posts 
Quote:
n = 0 mod 3, as well as finishing 2,LM to 1500. I am about 50% done with 2,1041+. 2,1426L and 2,1044+ will follow. I might get to 2,1101+ by the end of the year. If somone else wants to do it, go ahead. 

20060515, 01:29  #4  
Nov 2003
2^{2}×5×373 Posts 
Quote:
Of course it is a primitive root for some *subset* of M_q. This is to be expected. We expect 3 to be a quad residue 1/2 the time and a nonresidue 1/2 the time. We expect it to be a primitive root part of the time when it is a nonresidue. Why should this be surprising? 

20060515, 05:41  #5 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
What was a bit surprising was that so far, 3 seemed to be never a qth power for q≠3 and prime. However, that appears to be due to the small sample size we had:
Code:
? M=2^32171; ? Mod(3,M)^((M1)/13)==Mod(1,M) %8 = 1 Alex 
20060522, 17:39  #6  
Feb 2004
France
2×461 Posts 
Quote:
About q=1279 , (M1)/znorder(Mod(3,M)) says: 3 and Mod(3,M)^((M1)/3)==Mod(1,M) = 1 and Mod(3,M)^((M1)/5)==Mod(1,M) = 1 and Mod(3,M)^((M1)/7)==Mod(1,M) = 0 and Mod(3,M)^((M1)/11)==Mod(1,M) = 1 and Mod(3,M)^((M1)/13)==Mod(1,M) = 1 Can you explain ? Tony 

20060524, 20:13  #7 
Feb 2005
11111100_{2} Posts 
Essentially akruppa provided a counterexample to the original conjecture: 13 divides (M1)/znorder(Mod(3,M)) for M=2^32171 meaning that (M1)/znorder(Mod(3,M)) is not a power of 3 in this case.

20060524, 21:08  #8 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Tony,
if a prime q does not divide N1, then any residue (mod N) is a qth power. In fact under this condition, exponentiation by q is an automorphism on Z/ZN. Now, 5, 11 and 13 do not divide 2^12792, so the Mod(3,M)^((M1)/5) can be rewritten as, (Mod(3,M)^(M1))^(1/5) == Mod(1,M)^(1/5) == Mod(1,M), hence Pari prints a result of "1" for the equality. If q does divide N1, exponentiation by q is qto1 mapping and taking a qth root produces q solutions, so in this case we can't rewrite the exponent as in the last paragraph. Alex Last fiddled with by akruppa on 20060606 at 16:12 Reason: missing "1" 
20070324, 15:42  #9 
Feb 2004
France
2×461 Posts 
Have you got to it ?
T. Last fiddled with by T.Rex on 20070324 at 15:47 
20070326, 17:35  #10 
Nov 2003
2^{2}·5·373 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Higher order Wierferich prime pairs  carpetpool  Miscellaneous Math  2  20180415 00:28 
Factorial modulo a prime  axn  Computer Science & Computational Number Theory  66  20110901 21:55 
Order of 3 modulo a Mersenne prime  T.Rex  Math  7  20090313 10:46 
general form of the multiplicative order  juergen  Math  1  20040316 11:43 
Fast calculations modulo small mersenne primes like M61  Dresdenboy  Programming  10  20040229 17:27 