A062117 -id:A062117 - cp's OEIS frontend

A301916 Primes which divide numbers of the form 3^k + 1.

2, 5, 7, 17, 19, 29, 31, 37, 41, 43, 53, 61, 67, 73, 79, 89, 97, 101, 103, 113, 127, 137, 139, 149, 151, 157, 163, 173, 193, 197, 199, 211, 223, 233, 241, 257, 269, 271, 281, 283, 293, 307, 317, 331, 337, 349, 353, 367, 373, 379, 389, 397, 401, 409, 439

Offset: 1

Luke W. Richards, Mar 28 2018

nonn

This sequence can be used to factor P-1 values for prime candidates of the form 3^k+2, to aid with primality testing.
a(1) = 2 divides every number of the form 3^k+1. It is the only term with this property.
For k > 2, A000040(k) is a member if and only if A062117(k) is even. - Robert Israel, May 23 2018

			Every value of 3^k+1 is an even number, so 2 is in the sequence.
No values of 3^k+1 is ever a multiple of 3 for any integer k, so 3 is not in the sequence.
3^2+1 = 10, which is a multiple of 5, so 5 is in the sequence.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000040, A034472, A062117, A301917, A320481.

f:= p -> numtheory:-order(3,p)::even:
f(2):= true:
select(isprime and f, [2,seq(p,p=5..1000,2)]); # Robert Israel, May 23 2018

Join[{2}, Select[Range[5, 1000, 2], PrimeQ[#] && EvenQ@ MultiplicativeOrder[3, #]&]] (* Jean-François Alcover, Feb 02 2023 *)

isok(p)=if (p != 3, m = Mod(3, p); nb = znorder(m); for (k=1, nb, if (m^k == Mod(-1, p), return(1)););); return(0); \\ Michel Marcus, May 18 2018

list(lim)=my(v=List([2]),t); forfactored(n=4,lim\1+1, if(n[2][,2]==[1]~, my(p=n[1],m=Mod(3,p)); for(k=2,znorder(m,t), m*=3; if(m==-1, listput(v,p); break))); t=n); Vec(v) \\ Charles R Greathouse IV, May 23 2018

isok(p)=isprime(p)&&if(p<4,p==2,znorder(Mod(3,p))%2==0) \\ Jeppe Stig Nielsen, Jun 27 2020

isok(p)=!isprime(p)&&return(0); p<4&&return(p==2); s=valuation(p-1,2); Mod(3,p)^((p-1)>>s)!=1 \\ Jeppe Stig Nielsen, Jun 27 2020

A141350 Overpseudoprimes to base 3.

Original entry on oeis.org

121, 703, 3281, 8401, 12403, 31621, 44287, 47197, 55969, 74593, 79003, 88573, 97567, 105163, 112141, 211411, 221761, 226801, 228073, 293401, 313447, 320167, 328021, 340033, 359341, 432821, 443713, 453259, 478297, 497503, 504913, 679057, 709873, 801139, 867043, 894781, 973241, 1042417

Offset: 1

Vladimir Shevelev, Jun 27 2008, corrected Sep 07 2008

nonn

If h_3(n) is the multiplicative order of 3 modulo n, r_3(n) is the number of cyclotomic cosets of 3 modulo n then, by the definition, n is an overpseudoprime to base 3 if h_3(n)*r_3(n)+1=n. These numbers are in A020229.

In particular, if n is squarefree such that its prime factorization is n=p_1*...*p_k, then n is overpseudoprime of base 3 iff h_3(p_1)=...=h_3(p_k).

Amiram Eldar, Table of n, a(n) for n = 1..10798 (calculated using the b-file at A020229)
V. Shevelev, Overpseudoprimes, Mersenne Numbers and Wieferich Primes, arXiv:0806.3412 [math.NT], 2008-2012.
V. Shevelev, G. Garcia-Pulgarin, J. M. Velasquez and J. H. Castillo, Overpseudoprimes, and Mersenne and Fermat numbers as primover numbers, arXiv preprint arXiv:1206:0606 [math.NT], 2012. - From _N. J. A. Sloane_, Oct 28 2012
V. Shevelev, G. Garcia-Pulgarin, J. M. Velasquez and J. H. Castillo, Overpseudoprimes, and Mersenne and Fermat Numbers as Primover Numbers, J. Integer Seq. 15 (2012) Article 12.7.7.

Cf. A141232, A137576, A001262, A020229, A062117, A006694.

ops3Q[n_] := CompositeQ[n] && GCD[n, 3] == 1 && MultiplicativeOrder[3, n]*(DivisorSum[n, EulerPhi[#]/MultiplicativeOrder[3, #] &] - 1) + 1 == n; Select[Range[10^6], ops3Q] (* Amiram Eldar, Jun 24 2019 *)

isok(n) = (n!=1) && !isprime(n) && (gcd(n,3)==1) && (znorder(Mod(3,n)) * (sumdiv(n, d, eulerphi(d)/znorder(Mod(3, d))) - 1) + 1 == n); \\ Michel Marcus, Oct 25 2018

a(10)-a(38) from Gilberto Garcia-Pulgarin added by Vladimir Shevelev, Feb 06 2012

A372801 Order of 16 modulo the n-th prime: least k such that prime(n) divides 16^k-1.

Original entry on oeis.org

1, 1, 3, 5, 3, 2, 9, 11, 7, 5, 9, 5, 7, 23, 13, 29, 15, 33, 35, 9, 39, 41, 11, 12, 25, 51, 53, 9, 7, 7, 65, 17, 69, 37, 15, 13, 81, 83, 43, 89, 45, 95, 24, 49, 99, 105, 37, 113, 19, 29, 119, 6, 25, 4, 131, 67, 135, 23, 35, 47, 73, 51, 155, 39, 79, 15, 21, 173, 87, 22, 179

Offset: 2

Jianing Song, May 13 2024

a(n) is the period of the expansion of 1/prime(n) in hexadecimal.

Jianing Song, Table of n, a(n) for n = 2..10000

Cf. A302141 (order of 16 mod 2n+1).

In other bases: A014664, A062117, A082654, A211241, A211242, A211243, A211244, A211245, A002371.

PARI
```
a(n) = znorder(Mod(16, prime(n))).
```

a(n) = A014664(n)/gcd(4, A014664(n)) = A082654(n)/gcd(2, A082654(n)).

a(n) <= (prime(n) - 1)/2.

A201912 Irregular triangle of 2^k mod prime(n).

Original entry on oeis.org

0, 1, 2, 1, 2, 4, 3, 1, 2, 4, 1, 2, 4, 8, 5, 10, 9, 7, 3, 6, 1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1, 2, 4, 8, 16, 15, 13, 9, 1, 2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10, 1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12, 1, 2, 4, 8, 16, 3, 6, 12, 24

Offset: 1

T. D. Noe, Dec 17 2011

The row lengths are in A014664. For n > 1, the first term of each row is 1 and the last term is 2*prime(n)-1, which is A006254. Many sequences are in this one.

			The first 11 rows are:
2:  0;
3:  1, 2;
5:  1, 2, 4, 3;
7:  1, 2, 4;
11: 1, 2, 4, 8,  5, 10,  9,  7,  3,  6;
13: 1, 2, 4, 8,  3,  6, 12, 11,  9,  5, 10,  7;
17: 1, 2, 4, 8, 16, 15, 13,  9;
19: 1, 2, 4, 8, 16, 13,  7, 14,  9, 18, 17, 15, 11,  3,  6, 12,  5, 10;
23: 1, 2, 4, 8, 16,  9, 18, 13,  3,  6, 12;
29: 1, 2, 4, 8, 16,  3,  6, 12, 24, 19,  9, 18,  7, 14, 28, 27, 25, 21, 13, 26, 23, 17, 5, 10, 20, 11, 22, 15;
31: 1, 2, 4, 8, 16;

T. D. Noe, Rows n = 1..60, flattened

Cf. A062117, A201908, A201909, A201910, A201911.

Cf. similar sequences of the type 2^n mod p, where p is a prime: A000034 (p=3), A070402 (p=5), A069705 (p=7), A036117 (p=11), A036118 (p=13), A062116 (p=17), A036120 (p=19), A070335 (p=23), A036122 (p=29), A269266 (p=31), A036124 (p=37), A070348 (p=41), A070349 (p=43), A070351 (p=47), A036128 (p=53), A036129 (p=59), A036130 (p=61), A036131 (p=67), A036135 (p=83), A036138 (p=101), A036140 (p=107), A036144 (p=131), A036146 (p=139), A036147 (p=149), A036150 (p=163), A036152 (p=173), A036153 (p=179), A036154 (p=181), A036157 (p=197), A036159 (p=211), A036161 (p=227).

P:=Filtered([1..350],IsPrime);;
R:=List([1..Length(P)],n->OrderMod(2,P[n]));;
Flat(Concatenation([0],List([2..10],n->List([0..R[n]-1],k->PowerMod(2,k,P[n]))))); # Muniru A Asiru, Feb 01 2019

nn = 10; p = 2; t = p^Range[0,Prime[nn]]; Flatten[Table[If[Mod[n, p] == 0, {0}, tm = Mod[t, n]; len = Position[tm, 1, 1, 2][[-1,1]]; Take[tm, len-1]], {n, Prime[Range[nn]]}]]

A320481 Primes in A301916 but not in A045318.

Original entry on oeis.org

2, 769, 1297, 6529, 7057, 8017, 8737, 12097, 12289, 13297, 13441, 14929, 15073, 15361, 15937, 16273, 18913, 19441, 20593, 21601, 21649, 22273, 22369, 23857, 25633, 26017, 26449, 26497, 27793, 28513, 30529, 31249, 34369, 34849, 36913, 37057, 37441, 37633, 38833, 38977, 39409

Offset: 1

N. J. A. Sloane, Oct 17 2018

nonn

Is there a simpler characterization of these primes?
Answer from Don Reble, Oct 25 2018: (Start)
Let POT(x) be the largest power of 2 which divides x (A006519).
Apart from the initial 2, this sequence consists of those primes P such that
        2 <= POT(the order of 3 modulo P) <= POT(P-1)/8.
The condition "2 <=" ensures that P divides some 3^k+1, and the condition "<= POT(P-1)/8" is so that 3 has an eighth root modulo P.  A062117 is the order of 3 modulo prime(n). (End)
Comments from Richard Bumby, Nov 12 2018: (Start)
When considering methods for finding square roots mod p one is led to filtering the nonzero elements by the power of 2 dividing the multiplicative order of the element. The lowest level -- elements of odd order -- have easily computed square roots, and the square roots of other elements can be found if you can discover at least one element at a higher level.
To say that "x^8 = 3 has no solution mod p" is to say that 3 is in one of the top three levels and that there are more than 3 levels (so that 8 divides p-1).
To say that primes "divide numbers of the form 3^k + 1" is to say that -1 is a power of 3 mod p, or that 3 is not at the lowest level. If there are only four levels (9 mod 16), these statements are equivalent. Otherwise, the two statements are different. An interesting case has 3 at the second level, so that (-3) has odd order allowing cube roots of unity to be found quickly.
I was told that Odoni had some results on finding the number of primes with k levels for which a given number (e.g., 3) is at level j, but I never tracked down a reference. If the asymptotic behavior is what one would expect, A045318 and A301916 are really far from being "almost the same", except in the trivial sense of "zero density". (End)

Georg Fischer, email to N. J. A. Sloane, Oct 16 2018.

Ray Chandler, Table of n, a(n) for n = 1..10000

Cf. A006519, A045317, A045318, A062117, A301916, A301917.

Select[Prime@Range@4200,PowerModList[3,1/8,#]!={}&&IntegerQ@MultiplicativeOrder[3,#,-1]&] (* Giorgos Kalogeropoulos, Feb 23 2022 *)

More terms from Michel Marcus, Oct 17 2018

A263647 Numbers k such that 2^k-1 and 3^k-1 are coprime.

Original entry on oeis.org

1, 2, 3, 5, 7, 9, 13, 14, 15, 17, 19, 21, 25, 26, 27, 29, 31, 34, 37, 38, 39, 41, 45, 47, 49, 51, 53, 57, 59, 61, 62, 63, 65, 67, 71, 73, 74, 79, 81, 85, 87, 89, 91, 93, 94, 97, 98, 101, 103, 107, 109, 111, 113, 118, 122, 123, 125, 127, 133, 134, 135, 137, 139, 141, 142, 145, 147, 149, 151, 153, 157, 158, 159, 163, 167, 169, 171

Offset: 1

Robert Israel, Oct 22 2015

n such that there is no k for which both A014664(k) and A062117(k) divide n.
If n is in the sequence, then so is every divisor of n.
1 and 2 are the only members that are in A006093.
Conjectured to be infinite: see the Ailon and Rudnick paper.

			gcd(2^1-1, 3^1-1) = gcd(1,2) = 1, so a(1) = 1.
gcd(2^2-1, 3^2-1) = gcd(3,8) = 1, so a(2) = 2.
gcd(2^4-1, 3^4-1) = gcd(15,80) = 5, so 4 is not in the sequence.

Robert Israel, Table of n, a(n) for n = 1..10000
Nir Ailon, Zéev Rudnick, Torsion points on curves and common divisors of a^k - 1 and b^k - 1, Acta Arith. 113 (2004), 31-38. Also arXiv:math/0202102 [math.NT], 2002.
Thomas Bloom, Problem 820, Erdős Problems.

Cf. A000225, A006093, A024023, A014664, A062117.

[n: n in [1..200] | Gcd(2^n-1, 3^n-1) eq 1]; // Vincenzo Librandi, May 01 2016

select(n -> igcd(2^n-1,3^n-1)=1, [$1..1000]);

Select[Range[200], GCD[2^# - 1, 3^# - 1] == 1 &] (* Vincenzo Librandi, May 01 2016 *)

A344202 Primes p such that gcd(ord_p(2), ord_p(3)) = 1.

Original entry on oeis.org

683, 599479, 108390409, 149817457, 666591179, 2000634731, 4562284561, 14764460089, 24040333283, 2506025630791, 5988931115977

Offset: 1

Sofia Lacerda, May 11 2021

'ord_p' here means the multiplicative order, not to be confused with the p-adic order that is also often denoted by ord_p.

Related to Diophantine equations of the form (2^x-1)*(3^y-1) = n*z^2.

Sofia Lacerda, C++ program (github).
MathOverflow, Solve this Diophantine equation (2^x-1)(3^y-1)=2z^2
Mathematics Stack Exchange, For all alpha,beta in N, are there only finitely many primes so that gcd(ordp(alpha),ordp(beta))=1?, 2021.
Wikipedia, Multiplicative order.
Wikipedia, P-adic_valuation.

Cf. A014664, A062117.

Select[Range[10^6], PrimeQ[#] && CoprimeQ[MultiplicativeOrder[2, #], MultiplicativeOrder[3, #]] &] (* Amiram Eldar, May 11 2021 *)

isok(p) = isprime(p) && (gcd(znorder(Mod(2, p)), znorder(Mod(3, p))) == 1); \\ Michel Marcus, May 11 2021

from sympy.ntheory import n_order
from sympy import gcd, nextprime
A344202_list, p = [], 5
while p < 10**9:
    if gcd(n_order(2,p),n_order(3,p)) == 1:
        A344202_list.append(p)
    p = nextprime(p) # Chai Wah Wu, May 12 2021

a(3)-a(5) from Michel Marcus, May 11 2021
a(6)-a(8) from Amiram Eldar, May 11 2021
a(9) from Daniel Suteu, May 16 2021
a(10) from Sofia Lacerda, Jul 07 2021
a(11) from Sofia Lacerda, Aug 03 2021

A283620 a(n) is the least exponent k such that 3^k-1 is divisible by prime(n)^2, or -1 if no such k exists.

Original entry on oeis.org

2, -1, 20, 42, 5, 39, 272, 342, 253, 812, 930, 666, 328, 1806, 1081, 2756, 1711, 610, 1474, 2485, 876, 6162, 3403, 7832, 4656, 10100, 3502, 5671, 2943, 12656, 16002, 8515, 18632, 19182, 22052, 7550, 12246, 26406, 13861, 29756, 15931, 8145, 18145, 3088, 38612, 39402, 44310

Offset: 1

Michel Marcus, Mar 12 2017

a(2) is -1, because 3^n-1 cannot be divisible by prime(2)=3.
For some terms, prime(n)^2 is also the least square of prime which divides 3^a(n)-1. This is the case for n=1, 5, 6, ..., that is, p=2, 11, 13, ... (see A283454).
If n <> 2, then a(n) = A062117(n) if 3^A062117(n) == 1 (mod prime(n)^2), or
prime(n)*A062117(n) if not. - Robert Israel, Mar 16 2017

Robert Israel, Table of n, a(n) for n = 1..10000 (first 100 terms from Anton Mosunov)

Cf. A024023, A062117, A249025, A283454.

subs(FAIL=-1,[seq(numtheory:-order(3, ithprime(i)^2), i=1..100)]); # Robert Israel, Mar 16 2017

Join[{2,-1},Table[Module[{k=1},While[PowerMod[3,k,Prime[n]^2]!=1,k++];k],{n,3,50}]] (* Harvey P. Dale, Oct 22 2023 *)

a(n) = if (n == 2, -1, k = 1; p = prime(n); while((3^k-1) % p^2, k++); k;);

A383411 Primes p such that gcd(ord_p(3), ord_p(5)) = 1.

Original entry on oeis.org

2, 13, 313, 51169, 797161, 3482851, 5096867, 12207031, 162410641, 368385827, 1001523179, 4902814883, 104849105869, 131772143257, 572027881891

Offset: 1

Li GAN, Apr 26 2025

'ord_p' here means the multiplicative order modulo p, not to be confused with the p-adic order that is also often denoted by ord_p.

Mathematics Stack Exchange, For all alpha,beta in N, are there only finitely many primes so that gcd(ordp(alpha),ordp(beta))=1?, 2021.

Cf. A062117, A211241, A344202.

Select[Range[10000], PrimeQ[#] && CoprimeQ[MultiplicativeOrder[3, #], MultiplicativeOrder[5, #]] &]

forprime(p=13,oo,if(1==gcd(znorder(Mod(5,p)),znorder(Mod(3,p))),print1(p,", "))); \\ Joerg Arndt, Apr 26 2025

a(13)-a(15) from Bill McEachen, May 11 2025

A086087 a(n) is the minimal m such that the group GL(m,3) has an element of order n.

Original entry on oeis.org

1, 2, 2, 4, 2, 6, 2, 4, 4, 5, 4, 3, 6, 6, 4, 16, 4, 18, 4, 8, 5, 11, 4

Offset: 2

Yuval Dekel (dekelyuval(AT)hotmail.com), Aug 24 2003

For n > 2, a(prime(n)) = A062117(n). Also, for any n, a(n) <= n. - Eric M. Schmidt, May 18 2013

Cf. A085430, A053290.

A086087 := function(n) local m; if IsPrime(n) and n>3 then return Order(3*Z(n)^0); fi; m := 1; while true do if ForAny(ConjugacyClasses(GL(m, 3)), cc->Order(Representative(cc))=n) then return m; fi; m := m + 1; od; end; # Eric M. Schmidt, May 18 2013

Extended and corrected by Eric M. Schmidt, May 18 2013

cp's OEIS Frontend

A301916 Primes which divide numbers of the form 3^k + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

PARI

A141350 Overpseudoprimes to base 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A372801 Order of 16 modulo the n-th prime: least k such that prime(n) divides 16^k-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A201912 Irregular triangle of 2^k mod prime(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Mathematica

A320481 Primes in A301916 but not in A045318.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Extensions

A263647 Numbers k such that 2^k-1 and 3^k-1 are coprime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

A344202 Primes p such that gcd(ord_p(2), ord_p(3)) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica