A002326 -id:A002326 - cp's OEIS frontend

A070678 Smallest m in range 1..phi(n) such that 7^m == 1 mod n, or 0 if no such number exists.

0, 1, 1, 2, 4, 1, 0, 2, 3, 4, 10, 2, 12, 0, 4, 2, 16, 3, 3, 4, 0, 10, 22, 2, 4, 12, 9, 0, 7, 4, 15, 4, 10, 16, 0, 6, 9, 3, 12, 4, 40, 0, 6, 10, 12, 22, 23, 2, 0, 4, 16, 12, 26, 9, 20, 0, 3, 7, 29, 4, 60, 15, 0, 8, 12, 10, 66, 16, 22, 0, 70, 6, 24, 9, 4, 6, 0, 12

Offset: 1

N. J. A. Sloane and Amarnath Murthy, May 08 2002

nonn

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Cf. A070667-A070675, A002326, A070676, A053447, A070677, A070681, A053451, A070679, A070682, A070680, A070683.

[0] cat [Modorder(7, n): n in [2..100]]; // Vincenzo Librandi, Apr 01 2014

Table[SelectFirst[Range[EulerPhi[n]],PowerMod[7,#,n]==1&],{n,80}]/.(Missing["NotFound"]->0) (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Jan 25 2019 *)

A070679 Smallest m in range 1..phi(n) such that 9^m == 1 mod n, or 0 if no such number exists.

Original entry on oeis.org

0, 1, 0, 1, 2, 0, 3, 1, 0, 2, 5, 0, 3, 3, 0, 2, 8, 0, 9, 2, 0, 5, 11, 0, 10, 3, 0, 3, 14, 0, 15, 4, 0, 8, 6, 0, 9, 9, 0, 2, 4, 0, 21, 5, 0, 11, 23, 0, 21, 10, 0, 3, 26, 0, 10, 3, 0, 14, 29, 0, 5, 15, 0, 8, 6, 0, 11, 8, 0, 6, 35, 0, 6, 9, 0, 9, 15, 0, 39, 2, 0, 4, 41, 0

Offset: 1

N. J. A. Sloane and Amarnath Murthy, May 08 2002

nonn

Cf. A070667-A070675, A002326, A070676, A053447, A070677, A070681, A070678, A053451, A070682, A070680, A070683.

[0] cat [Modorder(9, n): n in [2..100]]; // Vincenzo Librandi, Apr 01 2014

Table[SelectFirst[Range[EulerPhi[n]],PowerMod[9,#,n]==1&],{n,90}]/. Missing[ "NotFound"] -> 0 (* Harvey P. Dale, Jan 22 2023 *)

a(n) = {for (i = 1, eulerphi(n), if ((9^i % n) == 1, return(i));); return (0);} \\Michel Marcus, Jul 31 2013

A068563 Numbers k such that 2^k == 4^k (mod k).

Original entry on oeis.org

1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 32, 36, 40, 42, 48, 54, 60, 64, 72, 80, 84, 96, 100, 108, 120, 126, 128, 136, 144, 156, 160, 162, 168, 180, 192, 200, 216, 220, 240, 252, 256, 272, 288, 294, 300, 312, 320, 324, 336, 342, 360, 378, 384, 400, 408, 420, 432, 440

Offset: 1

Benoit Cloitre, Mar 25 2002

If k is in the sequence then 2k is also in the sequence, but the converse is not true.
Contains A124240 as a subsequence. Their difference is given by A124241. - T. D. Noe, May 30 2003
Also, integers k such that A007733(k) divides k. Also, integers k such that for every odd prime divisor p of k, A007733(p) = A002326((p-1)/2) divides k. Also, integers k such that A000265(k) divides 2^k-1. - Max Alekseyev, Aug 25 2013

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Eric Weisstein's World of Mathematics, Carmichael Function.

Cf. A000265, A002322, A002326, A007733, A124240, A124241.

Select[Range[500], PowerMod[2,#,# ] == PowerMod[4,#,# ] & ]

isok(k) = Mod(2, k)^k == Mod(4, k)^k; \\ Amiram Eldar, Apr 19 2025

Comment and Mathematica program corrected by T. D. Noe, Oct 17 2008

A070676 Smallest m in range 1..phi(n) such that 3^m == 1 mod n, or 0 if no such number exists.

Original entry on oeis.org

0, 1, 0, 2, 4, 0, 6, 2, 0, 4, 5, 0, 3, 6, 0, 4, 16, 0, 18, 4, 0, 5, 11, 0, 20, 3, 0, 6, 28, 0, 30, 8, 0, 16, 12, 0, 18, 18, 0, 4, 8, 0, 42, 10, 0, 11, 23, 0, 42, 20, 0, 6, 52, 0, 20, 6, 0, 28, 29, 0, 10, 30, 0, 16, 12, 0, 22, 16, 0, 12, 35, 0, 12, 18, 0, 18, 30, 0

Offset: 1

N. J. A. Sloane and Amarnath Murthy, May 08 2002

nonn

Cf. A070667-A070675, A002326, A053447, A070677, A070681, A070678, A053451, A070679, A070682, A070680, A070683.

[0] cat [Modorder(3, n): n in [2..100]]; // Vincenzo Librandi, Apr 01 2014

Table[SelectFirst[Range[EulerPhi[n]],PowerMod[3,# ,n]==1&,0],{n,80}] (* The program uses the SelectFirst function from Mathematica version 10 *) (* Harvey P. Dale, Aug 18 2015 *)

A070680 Smallest m in range 1..phi(n) such that 11^m == 1 mod n, or 0 if no such number exists.

Original entry on oeis.org

0, 1, 2, 2, 1, 2, 3, 2, 6, 1, 0, 2, 12, 3, 2, 4, 16, 6, 3, 2, 6, 0, 22, 2, 5, 12, 18, 6, 28, 2, 30, 8, 0, 16, 3, 6, 6, 3, 12, 2, 40, 6, 7, 0, 6, 22, 46, 4, 21, 5, 16, 12, 26, 18, 0, 6, 6, 28, 58, 2, 4, 30, 6, 16, 12, 0, 66, 16, 22, 3, 70, 6, 72, 6, 10, 6, 0, 12, 39, 4

Offset: 1

N. J. A. Sloane and Amarnath Murthy, May 08 2002

nonn

Cf. A070667-A070675, A002326, A070676, A053447, A070677, A070681, A070678, A053451, A070679, A070682, A070683.

[0] cat [Modorder(11, n): n in [2..100]]; // Vincenzo Librandi, Apr 01 2014

Table[SelectFirst[Range[EulerPhi[n]],PowerMod[11,#,n]==1&,0],{n,80}] (* Paul F. Marrero Romero, Oct 21 2024 *)

A070681 Smallest m in range 1..phi(2n+1) such that 6^m == 1 mod 2n+1, or 0 if no such number exists.

Original entry on oeis.org

0, 0, 1, 2, 0, 10, 12, 0, 16, 9, 0, 11, 5, 0, 14, 6, 0, 2, 4, 0, 40, 3, 0, 23, 14, 0, 26, 10, 0, 58, 60, 0, 12, 33, 0, 35, 36, 0, 10, 78, 0, 82, 16, 0, 88, 12, 0, 9, 12, 0, 10, 102, 0, 106, 108, 0, 112, 11, 0, 16, 110, 0, 25, 126, 0, 130, 18, 0, 136, 23, 0, 60

Offset: 0

N. J. A. Sloane and Amarnath Murthy, May 08 2002

nonn

Cf. A070667-A070675, A002326, A070676, A053447, A070677, A070678, A053451, A070679, A070682, A070680, A070683.

A144755 Primes which divide none of overpseudoprimes to base 2 (A141232).

Original entry on oeis.org

2, 3, 5, 7, 11, 13, 17, 19, 31, 41, 43, 73, 127, 151, 241, 257, 331, 337, 683, 2731, 5419, 8191, 43691, 61681, 65537, 87211, 131071, 174763, 262657, 524287, 599479, 2796203, 15790321, 18837001, 22366891, 715827883, 2147483647, 4278255361

Offset: 1

Vladimir Shevelev, Sep 20 2008

nonn

Odd prime p is in the sequence iff A064078(A002326((p-1)/2))=p. For example, for p=127 we have A002326((127-1)/2)=7 and A064078(7)=127. Thus p=127 is in the sequence.
Primes p such that the binary expansion of 1/p has a unique period length; that is, no other prime has the same period. Sequence A161509 sorted. - T. D. Noe, Apr 13 2010
Since A161509 has terms of varying magnitude, sorting any finite initial segment of A161509 cannot provide a guarantee that there are no other terms missed in between. Any prime p not (yet) appearing in A161509 should be tested via A064078(A002326((p-1)/2))=p to conclude whether it belongs to the current sequence. - Max Alekseyev, Feb 10 2024

			Overpseudoprimes to base 2 are odd, then a(1)=2.

Cf. A141232, A002326, A064078, A112927.

Cf. A040017 (unique-period primes in base 10). - T. D. Noe, Apr 13 2010

b=2; t={}; Do[c=Cyclotomic[n,b]; q=c/GCD[n,c]; If[PrimePowerQ[q], p=FactorInteger[q][[1,1]]; If[p<10^12, AppendTo[t,p]; Print[{n,p}]]], {n,1000}]; t=Sort[t] (* T. D. Noe, Apr 13 2010 *)

{ is_a144755(p) = my(q,m,g); q=znorder(Mod(2,p)); m=2^q-1; fordiv(q,d, if(d1,m\=g))); m==p; } \\ Max Alekseyev, Feb 10 2024

Extended by T. D. Noe, Apr 13 2010

b-file deleted by Max Alekseyev, Feb 10 2024.

A081858 Numbers k such that 2*k+1 divides 2^k-1.

Original entry on oeis.org

0, 3, 8, 11, 15, 20, 23, 35, 36, 39, 44, 48, 51, 56, 63, 68, 75, 83, 95, 96, 99, 111, 116, 119, 120, 128, 131, 135, 140, 155, 156, 168, 170, 176, 179, 183, 191, 200, 204, 215, 216, 219, 224, 228, 231, 239, 243, 251, 260, 280, 284, 288, 296, 299, 300, 303, 308

Offset: 1

Benoit Cloitre, Apr 11 2003

nonn

From Chris Boyd, Mar 16 2014: (Start)
n is a term if and only if n=0, 2n+1 is a prime of the form 8k+-1, or 2n+1 is an Euler pseudoprime satisfying 2^n == 1 mod 2n+1.
Case 1: 0 is a term. Case 2, 2n+1 prime: by Euler's criterion and the quadratic character of 2, 2^n == 1 mod 2n+1 only if 2n+1 is of the form 8k+-1. Case 3, 2n+1 composite: 2^n == 1 mod 2n+1 only if 2n+1 is one of the subset of Euler pseudoprimes satisfying 2^n == 1 mod 2n+1.
The first term for which 2n+1 is a qualifying Euler pseudoprime is n=170.
The first Euler pseudoprime that does not correspond to a term is 3277, because 2^((3277-1)/2) == -1 mod 3277. (End)

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A002326, A014664.

Join[{0}, Select[Range[300], PowerMod[2, #, 2*# + 1] === 1 &]] (* Amiram Eldar, Jun 02 2022 *)

isok(n) = !((2^n-1) % (2*n+1)); \\ Michel Marcus, Dec 04 2013

for(n=0,400,if(n%znorder(Mod(2,2*n+1))==0,print1(n","))) \\ Chris Boyd, Mar 16 2014, after Michael Somos in A002326

k such that A002326(k)|k: since 2^k == 1 mod 2*k+1, k must be a multiple of the order of 2 mod 2*k+1.

Formula corrected by Chris Boyd, Mar 16 2014

A037226 a(n) = phi(2n+1) / multiplicative order of 2 mod 2n+1.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 2, 2, 1, 1, 1, 6, 2, 2, 1, 2, 2, 3, 2, 2, 2, 4, 1, 2, 2, 1, 1, 6, 4, 1, 2, 2, 8, 2, 2, 2, 1, 1, 8, 2, 8, 6, 6, 2, 2, 2, 1, 2, 4, 1, 3, 2, 4, 2, 6, 4, 1, 4, 1, 18, 6, 1, 6, 2, 2, 1, 2, 2, 4, 2, 1, 10, 4, 6, 3, 2, 4

Offset: 0

N. J. A. Sloane

nonn

Number of primitive irreducible factors of x^(2n+1) - 1 over integers mod 2. There are no primitive irreducible factors for x^(2n)-1 because it always has the same factors as x^n-1. Considering that A000374 also counts the cycles in the map f(x) = 2x mod n, a(n) is also the number of primitive cycles of that mapping. - T. D. Noe, Aug 01 2003

Equals number of irreducible factors of the cyclotomic polynomial Phi(2n+1,x) over Z/2Z. All factors have the same degree. - T. D. Noe, Mar 01 2008

T. D. Noe, Table of n, a(n) for n = 0..10000
Brillhart, John; Lomont, J. S.; Morton, Patrick. Cyclotomic properties of the Rudin-Shapiro polynomials, J. Reine Angew. Math.288 (1976), 37--65. See Table 2. MR0498479 (58 #16589).
Jarkko Peltomäki and Aleksi Saarela, Standard words and solutions of the word equation X_1^2 ... X_n^2 = (X_1 ... X_n)^2, Journal of Combinatorial Theory, Series A (2021) Vol. 178, 105340. See also arXiv:2004.14657 [cs.FL], 2020.

Cf. A000374 (number of irreducible factors of x^n - 1 over integers mod 2), A081844.

Cf. A006694 (cyclotomic cosets of 2 mod 2n+1).

a[n_] := EulerPhi[2n+1]/MultiplicativeOrder[2, 2n+1]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Dec 10 2015 *)

a(n)=eulerphi(2*n+1)/znorder(Mod(2,2*n+1)) \\ Charles R Greathouse IV, Dec 29 2013

a(n) = Sum{d|2n+1} mu((2n+1)/d) A000374(d), the inverse Mobius transform of A000374 - T. D. Noe, Aug 01 2003

a(n) = A037225(n)/A002326(n).

A139035 Primes of the form 4*k+3 with primitive root -2.

Original entry on oeis.org

7, 23, 47, 71, 79, 103, 167, 191, 199, 239, 263, 271, 311, 359, 367, 383, 463, 479, 487, 503, 599, 607, 647, 719, 743, 751, 823, 839, 863, 887, 967, 983, 991, 1031, 1039, 1063, 1087, 1151, 1223, 1231, 1279, 1303, 1319, 1367, 1439, 1447, 1487, 1511, 1543, 1559

Offset: 1

Vladimir Shevelev, May 31 2008, Jun 06 2008

nonn

Original name: Primes with semiprimitive root 2.
If p is a prime, then we call r a semiprimitive root if it has order (p-1)/2 and there is no x for which a^x is congruent to -1 (mod p).  So +/- r^k, 0 <= k <= (p-3)/2 is a complete set of nonzero residues (mod p).
If r=2, then (-1/p)=-1 and, consequently, a(n)==-1(mod 4).
Besides, (2/a(n))=1. Indeed, since 2^((p-1)/2)=1 (mod p), then 2==2^((p+1)/2)=(2^((p+1)/4))^2. Therefore, (a(n))^2==1(mod 16) and thus a(n)==-1(mod 8). This yields that residues 1,2,...,2^((p-3)/2) are quadratic residues modulo a(n), while -1,-2,...,-2^((p-3)/2) are quadratic nonresidues modulo a(n). Primitive root of a(n) is greater than or equal to 3. All terms are in A115591.
Conjecture: primes that have both primitive root -2 and -4. - Davide Rotondo, Dec 20 2024

Amiram Eldar, Table of n, a(n) for n = 1..10000
Christian Elsholtz, Almost all primes have a multiple of small Hamming weight, arXiv:1602.05974 [math.NT], 2016. See p. 6.
Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv preprint arXiv:1608.00862 [math.GM], 2016.
Vladimir Shevelev, On the Newman sum over multiples of a prime with a primitive or semiprimitive root 2, arXiv:0710.1354 [math.NT], 2007.
Vladimir Shevelev Exact exponent in the remainder term of Gelfond's digit theorem in the binary case, Acta Arithm. 136 (2009) 91-100, eq. (10).

Cf. A006694, A002326, A064287, A001917, A001122, A133954, A115591.

Reap[For[p = 3, p <= 10^4, p = NextPrime[p], rp = MultiplicativeOrder[2, p]; rm = MultiplicativeOrder[-2, p]; If[rp != p-1 && rm == p-1, Sow[p]]] ][[2, 1]] (* Jean-François Alcover, Sep 03 2016, after Joerg Arndt *)

{ forprime (p=3, 10^4,
    rp = znorder(Mod(+2,p));
    rm = znorder(Mod(-2,p));
    if ( (rp!=p-1) && (rm==p-1), print1(p,", ") );
);}
/* Joerg Arndt, Jun 03 2012 */

is(n)=n%8==7 && isprime(n) && znorder(Mod(-2,n))==n-1 \\ Charles R Greathouse IV, Nov 30 2017

Prime p is in the sequence iff p==-1(mod 8) and A002326((p-1)/2)=(p-1)/2. A sufficient condition: if p==-1 (mod 8) and (p-1)/2 is prime, then p is in the sequence (the converse statement, generally speaking, is not true).

A006694((a(n)-1)/2)=2 and A064287((a(n)-1)/2)=1.

New name from Joerg Arndt, Jun 03 2012

cp's OEIS Frontend

A070678 Smallest m in range 1..phi(n) such that 7^m == 1 mod n, or 0 if no such number exists.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

A070679 Smallest m in range 1..phi(n) such that 9^m == 1 mod n, or 0 if no such number exists.

Views

Author

Keywords

Crossrefs

Programs

Magma

Mathematica

PARI

A068563 Numbers k such that 2^k == 4^k (mod k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A070676 Smallest m in range 1..phi(n) such that 3^m == 1 mod n, or 0 if no such number exists.

Views

Author

Keywords

Crossrefs

Programs

Magma

Mathematica

A070680 Smallest m in range 1..phi(n) such that 11^m == 1 mod n, or 0 if no such number exists.

Views

Author

Keywords

Crossrefs

Programs

Magma

Mathematica

A070681 Smallest m in range 1..phi(2n+1) such that 6^m == 1 mod 2n+1, or 0 if no such number exists.

Views

Author

Keywords

Crossrefs

A144755 Primes which divide none of overpseudoprimes to base 2 (A141232).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Extensions

A081858 Numbers k such that 2*k+1 divides 2^k-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A037226 a(n) = phi(2n+1) / multiplicative order of 2 mod 2n+1.

Views

Author

Keywords

Comments