OFFSET
1,2
COMMENTS
In elementary terms, a(n) is the exponent m in [0, p-1] with 3^((M-1)/p) == 2^m (mod M), where (M-1)/p = (2^p-2)/p and M = 2^p-1 is prime.
Equivalently it is the base-2 discrete logarithm of 3^((M-1)/p) in the order-p subgroup of (Z/M)*. This is canonical, not arbitrary: 2 has order exactly p modulo M (2^p == 1 but 2^d != 1 for 0 < d < p), so <2> = {1, 2, ..., 2^(p-1)} IS that subgroup; and since (Z/M)* is cyclic of order M-1 = p*((M-1)/p), the ((M-1)/p)-th power map carries it onto <2>, so 3^((M-1)/p) -- indeed a^((M-1)/p) for any a coprime to M -- lies in <2>. This sequence takes a = 3, the smallest base above 2.
The analogous projection to the order-2 subgroup is the classical fact 3^((M-1)/2) == -1 (mod M): 3 is a quadratic nonresidue modulo every Mersenne prime, by quadratic reciprocity (M == 1 (mod 3) and (M-1)/2 is odd).
REFERENCES
K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, 2nd ed., GTM 84, Springer, 1990, Proposition 9.1.4, pp. 110-111.
FORMULA
a(n) is the unique k with 0 <= k < p and 3^((M-1)/p) == 2^k (mod M), where p = A000043(n+1) and M = A000668(n+1).
For p >= 5, a(n) == 2*L (mod p), where L is the unique integer in [0, p-1] with 2^L == (1-w)^((M-1)/p) (mod M) and w is a primitive cube root of unity in (Z/M)* (L is independent of the choice of w). This follows from the factorization 3 = -w^2*(1-w)^2 in the ring of Eisenstein integers Z[w].
EXAMPLE
For n = 1: p = 3, M = 7. We have 3^((7-1)/3) = 3^2 == 2 (mod 7). Since 2^1 = 2, we get a(1) = 1.
For n = 2: p = 5, M = 31. We have 3^((31-1)/5) = 3^6 == 16 (mod 31). Since 2^4 = 16, we get a(2) = 4.
For n = 3: p = 7, M = 127. We have 3^((127-1)/7) = 3^18 == 4 (mod 127). Since 2^2 = 4, we get a(3) = 2.
For n = 4: p = 13, M = 8191. We have 3^((8191-1)/13) = 3^630 == 4096 (mod 8191). Since 2^12 = 4096, we get a(4) = 12.
MATHEMATICA
m3[p_] := Module[{M = 2^p - 1, nR, target, val = 1, k = 0},
If[! PrimeQ[M], Return[Null]];
nR = (M - 1)/p; target = PowerMod[3, nR, M];
While[val =!= target && k < p, val = Mod[2 val, M]; k++]; k];
(* baby-step/giant-step: O(sqrt p) search; reproduces the full DATA *)
m3BSGS[p_] := Module[{M = 2^p - 1, nR, target, s, baby, v = 1, step, g, res = Null},
If[! PrimeQ[M], Return[Null]];
nR = (M - 1)/p; target = PowerMod[3, nR, M]; s = Floor[Sqrt[p]] + 1;
baby = Association[]; Do[baby[v] = j; v = Mod[2 v, M], {j, 0, s - 1}];
step = PowerMod[2, -s, M]; g = target;
Do[If[KeyExistsQ[baby, g] && 0 <= i s + baby[g] < p,
res = i s + baby[g]; Break[]];
g = Mod[g step, M], {i, 0, s}];
res];
Table[m3BSGS[MersennePrimeExponent[n + 1]], {n, 1, 20}]
PROG
(PARI) m3(p) = {my(M = 2^p - 1, nR = (M-1)/p, t = Mod(3, M)^nR, v = Mod(1, M));
for(k = 0, p-1, if(v == t, return(k)); v *= 2); }
\\ v was taken from A000043
my(v = [3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091]); for(i = 1, #v, print1(m3(v[i]), ", "))
(Python)
from sympy import isprime
def m3(p):
M = 2**p - 1
assert isprime(M)
nR = (M - 1) // p
target = pow(3, nR, M)
val = 1
for k in range(p):
if val == target:
return k
val = (val * 2) % M
(Python) # baby-step/giant-step, for large p (e.g. p >= 10^5)
from sympy import isprime
import math, gmpy2
from gmpy2 import mpz, powmod, invert
def m3_bsgs(p):
M = mpz(2)**p - 1
assert isprime(int(M))
nR = (M - 1) // p
target = powmod(mpz(3), nR, M)
s = int(math.isqrt(p)) + 1
baby = {}; v = mpz(1)
for j in range(s):
baby[int(v)] = j; v = (v * 2) % M
step = invert(powmod(mpz(2), s, M), M)
g = target
for i in range(s):
if int(g) in baby:
k = i * s + baby[int(g)]
if 0 <= k < p:
return k
g = (g * step) % M
return None
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Michael C.H. Lin, May 26 2026
STATUS
approved