mersenneforum.org > Math Conjecture about multiplicative order of 3 modulo a Mersenne prime
 Register FAQ Search Today's Posts Mark Forums Read

 2006-05-14, 14:35 #1 T.Rex     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 (Mq-1)/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. $\large \frac{M_q-1}{order(3,M_q)}=3^n \ \ \text{with} \ \ n=0,1,2 \$ Any idea to prove it or to compute more examples ? Tony Data: Code: q (Mq-1)/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 PARI/gp program used (download Cunningham 2-table here): Code: \r cunn2.gp mo3(q) = { M=2^q-1; (M-1)/znorder(Mod(3,M)) }
 2006-05-14, 19:01 #2 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts For all known prime factors q of M2203-1, 3 is not a q-th 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^2203-1; ? 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)^((M-1)/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 2006-05-14 at 19:41
2006-05-15, 01:21   #3
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by akruppa For all known prime factors q of M2203-1, 3 is not a q-th power (mod M2203). However, 2^1101+1 is not completely factored, a c217 remains. This would make a pretty attractive target for SNFS.
It is on my long range "todo" list. I am slowly doing all 2^n+1 n < 1200 for
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.

2006-05-15, 01:29   #4
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by T.Rex In thread LLT DiGraph, maxal had the idea to compute (Mq-1)/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. $\large \frac{M_q-1}{order(3,M_q)}=3^n \ \ \text{with} \ \ n=0,1,2 \$ Any idea to prove it or to compute more examples ?

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
non-residue 1/2 the time. We expect it to be a primitive root part of the
time when it is a non-residue.

Why should this be surprising?

 2006-05-15, 05:41 #5 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts What was a bit surprising was that so far, 3 seemed to be never a q-th power for q≠3 and prime. However, that appears to be due to the small sample size we had: Code: ? M=2^3217-1; ? Mod(3,M)^((M-1)/13)==Mod(1,M) %8 = 1 so 3 is a 13-th power (mod M3217). Alex
2006-05-22, 17:39   #6
T.Rex

Feb 2004
France

2×461 Posts

Quote:
 Originally Posted by akruppa What was a bit surprising was that so far, 3 seemed to be never a q-th power for q≠3 and prime. However, that appears to be due to the small sample size we had.
I do not understand your reasoning.
(M-1)/znorder(Mod(3,M)) says: 3
and Mod(3,M)^((M-1)/3)==Mod(1,M) = 1
and Mod(3,M)^((M-1)/5)==Mod(1,M) = 1
and Mod(3,M)^((M-1)/7)==Mod(1,M) = 0
and Mod(3,M)^((M-1)/11)==Mod(1,M) = 1
and Mod(3,M)^((M-1)/13)==Mod(1,M) = 1

Can you explain ?

Tony

 2006-05-24, 20:13 #7 maxal     Feb 2005 111111002 Posts Essentially akruppa provided a counterexample to the original conjecture: 13 divides (M-1)/znorder(Mod(3,M)) for M=2^3217-1 meaning that (M-1)/znorder(Mod(3,M)) is not a power of 3 in this case.
 2006-05-24, 21:08 #8 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts Tony, if a prime q does not divide N-1, then any residue (mod N) is a q-th power. In fact under this condition, exponentiation by q is an automorphism on Z/ZN. Now, 5, 11 and 13 do not divide 2^1279-2, so the Mod(3,M)^((M-1)/5) can be rewritten as, (Mod(3,M)^(M-1))^(1/5) == Mod(1,M)^(1/5) == Mod(1,M), hence Pari prints a result of "1" for the equality. If q does divide N-1, exponentiation by q is q-to-1 mapping and taking a q-th 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 2006-06-06 at 16:12 Reason: missing "-1"
2007-03-24, 15:42   #9
T.Rex

Feb 2004
France

2×461 Posts

Quote:
 Originally Posted by R.D. Silverman I might get to 2,1101+ by the end of the year.
Have you got to it ?
T.

Last fiddled with by T.Rex on 2007-03-24 at 15:47

2007-03-26, 17:35   #10
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by T.Rex Have you got to it ? T.

For the time being, at least, I do not have the CPU resources.

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 2 2018-04-15 00:28 axn Computer Science & Computational Number Theory 66 2011-09-01 21:55 T.Rex Math 7 2009-03-13 10:46 juergen Math 1 2004-03-16 11:43 Dresdenboy Programming 10 2004-02-29 17:27

All times are UTC. The time now is 10:56.

Thu Dec 2 10:56:50 UTC 2021 up 132 days, 5:25, 0 users, load averages: 1.62, 1.42, 1.30