mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2006-05-14, 14:35   #1
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2×461 Posts
Default 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))
}
T.Rex is offline   Reply With Quote
Old 2006-05-14, 19:01   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2006-05-15, 01:21   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2006-05-15, 01:29   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

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?
R.D. Silverman is offline   Reply With Quote
Old 2006-05-15, 05:41   #5
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2006-05-22, 17:39   #6
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2×461 Posts
Default

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.
About q=1279 ,
(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
T.Rex is offline   Reply With Quote
Old 2006-05-24, 20:13   #7
maxal
 
maxal's Avatar
 
Feb 2005

111111002 Posts
Default

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.
maxal is offline   Reply With Quote
Old 2006-05-24, 21:08   #8
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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"
akruppa is offline   Reply With Quote
Old 2007-03-24, 15:42   #9
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2×461 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
T.Rex is offline   Reply With Quote
Old 2007-03-26, 17:35   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

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

For the time being, at least, I do not have the CPU resources.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Higher order Wierferich prime pairs carpetpool Miscellaneous Math 2 2018-04-15 00:28
Factorial modulo a prime axn Computer Science & Computational Number Theory 66 2011-09-01 21:55
Order of 3 modulo a Mersenne prime T.Rex Math 7 2009-03-13 10:46
general form of the multiplicative order juergen Math 1 2004-03-16 11:43
Fast calculations modulo small mersenne primes like M61 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

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.