A046145 -id:A046145 - cp's OEIS frontend

A285512 a(n) = smallest integer m>0 such that the positive integers not exceeding m and coprime to n generate the multiplicative group U(Z/nZ).

1, 1, 2, 3, 2, 5, 3, 5, 2, 3, 2, 7, 2, 3, 7, 5, 3, 5, 2, 11, 5, 7, 5, 13, 2, 5, 2, 5, 2, 11, 3, 5, 5, 3, 3, 7, 2, 3, 7, 11, 3, 11, 3, 7, 7, 5, 5, 13, 3, 3, 5, 5, 2, 5, 3, 11, 5, 3, 2, 13, 2, 3, 5, 5, 3, 7, 2, 5, 5, 19, 7, 13, 5, 5

Offset: 1

Max Alekseyev and Thomas Ordowski, Apr 20 2017

nonn

Denoted G(n) in Burthe (1997).
If A046145(n)>0, then a(n) <= A046145(n).
For all n>=3, a(n) is prime.

Burthe, R. J., Jr. Upper bounds for least witnesses and generating sets. Acta Arith. 80:4 (1997), 311-326.
Wikipedia, Multiplicative group of integers modulo n.

Cf. A002997, A046145, A285513, A285514.

{ A285512(n) = my(S,s,t); S=Set([Mod(1,n)]); t=1; while( #S!=eulerphi(n), until(n%t,t=nextprime(t+1)); until(#S==s, s=#S; S=setunion(S,Set(S*t))); ); t; }

A206550 Smallest positive primitive roots Modd n.

Original entry on oeis.org

0, 1, 1, 3, 3, 5, 3, 3, 5, 3, 3, 0, 7, 5, 7, 3, 3, 5, 3, 0, 11, 3, 3, 0, 3, 7, 5, 0, 3, 0, 3, 3, 5, 3, 3, 0, 5, 13, 7, 0, 7, 0, 3, 0, 7, 3, 3, 0, 3, 3, 5, 0, 3, 5, 3, 0, 5, 3, 3, 0, 7, 7, 0, 3, 0, 0, 7, 0, 7, 0, 3, 0, 5, 5, 13, 0, 3, 0, 3, 0, 5, 7, 3, 0, 0, 5, 11

Offset: 1

Wolfdieter Lang, Mar 27 2012

nonn

For multiplication Modd n (not to be confused with mod n) see a comment on A203571.
The 0 for n=1 is a primitive root Modd 1, the other zeros indicate that there is no primitive root for this n.
Iff a(n)>0, for n>=2, then the Galois group Gal(Q(2*cos(Pi/n))/Q), which is the multiplicative group of odd reduced residue classes Modd n (hence the notation Modd) is cyclic. For n=1 this group is also cyclic. See A206551 (cyclic moduli n) and A206552 (acyclic, i.e. non-cyclic, moduli n). [Changed by Wolfdieter Lang, Apr 04 2012]

			n=1: delta(1) = 1, a(1) = 1 == 0 (Modd 1): 0^1 = 0 == 1 (Modd 1).
n=2: delta(2) = 1, a(2) = 1 == 1 (Modd 2): 1^1 = 1 == 1 (Modd 2).
n=4: delta(4) = 2, a(2) = 3 == 3 (Modd 4): 3^2 = 9 == 1 (Modd 4).
n=6: delta(4) = 2, a(6) = 5 == 5 (Modd 6): 5^2 = 25. 25 (Modd 6) = 25 (mod 6) =1.
n=12: delta(12) = 4, a(12) = 0, because no primitive root exists: 5^2 == 1 (Modd 12), 7^2 == 1 (Modd 12) and 11^2 == 1 (Modd 12). The cycle structure of this acyclic group is [[5,1],[7,1],[11,1]]. It is the (abelian) group Z_2 x Z_2.

Cf. A046145 (mod n case).

a(1) = 0 == 1 (Modd 1).

If no primitive root exists for n>=2 then a(n):=0. If a primitive root exists for n>=2 then a(n) is the smallest positive integer whose order Modd n is delta(n), with delta(n) = A055034(n). That is, with gcd(a(n),2*n) = 1, n>=2, the least positive exponent k such that a(n)^k == 1 (Modd n) is delta(n), and a(n) is the smallest positive representative Modd n with this property.

A103336 Numbers whose largest primitive root (A046146) is not prime.

Original entry on oeis.org

1, 2, 11, 17, 19, 23, 29, 31, 37, 38, 41, 43, 47, 53, 58, 59, 62, 67, 71, 73, 74, 79, 81, 82, 83, 86, 89, 94, 97, 101, 107, 113, 118, 121, 122, 125, 127, 131, 134, 137, 139, 146, 149, 151, 157, 158, 162, 163, 167, 173, 178, 179, 191, 193, 194, 197, 211, 218, 223

Offset: 1

Harry J. Smith, Jan 31 2005

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Primitive Root.

Cf. A001918, A046144, A046145, A046146, A103309, A103310, A103335, A103337, A103338.

Select[Range[250], #==1 || ((p = PrimitiveRootList[#]) != {} && ! PrimeQ[Max @ p]) &] (* Amiram Eldar, Sep 25 2021 *)

Offset corrected by Amiram Eldar, Sep 25 2021

A103337 Smallest primitive root of numbers in sequence A103335.

Original entry on oeis.org

0, 1, 6, 6, 6, 6, 6, 6, 10, 10, 21, 6, 21, 15, 15, 15, 15, 6, 6, 21, 15, 6, 6, 10, 14, 6, 6, 10, 6, 6, 6, 14, 6, 6, 10, 6, 6, 14, 10, 6, 21, 10, 35, 6, 6, 6, 15, 6, 6, 10, 21, 14, 6, 33, 6, 6, 10, 6, 6, 6, 10, 6, 22, 15, 15, 6, 10, 12, 6, 15, 15, 10, 14, 21, 6, 15, 6, 6, 6, 6, 6, 6, 6, 10, 10, 6

Offset: 1

Harry J. Smith, Jan 31 2005

nonn

Robert Israel, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Primitive Root.

Cf. A001918, A046144, A046145, A046146, A103309, A103310, A103335, A103336, A103338.

# given list A103335 as at that sequence
[0,seq(numtheory:-primroot(A103335[i]),i=2..nops(A103335))]; # Robert Israel, Sep 08 2020

Offset changed by Robert Israel, Sep 08 2020

A103338 Largest primitive root of numbers in sequence A103336.

Original entry on oeis.org

0, 1, 8, 14, 15, 21, 27, 24, 35, 33, 35, 34, 45, 51, 55, 56, 55, 63, 69, 68, 69, 77, 77, 75, 80, 77, 86, 91, 92, 99, 104, 110, 115, 117, 115, 123, 118, 128, 117, 134, 135, 141, 147, 146, 152, 153, 155, 159, 165, 171, 175, 176, 189, 188, 189, 195, 207, 207, 214

Offset: 1

Harry J. Smith, Jan 31 2005

nonn

Robert Israel, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Primitive Root.

Cf. A001918, A046144, A046145, A046146, A103309, A103310, A103335, A103336, A103337.

f:= proc(n) local m; uses NumberTheory;
  if n::odd then
    if NumberOfPrimeFactors(n,distinct) > 1 then return NULL fi;
  elif n mod 4 = 0 or NumberOfPrimeFactors(n,distinct) > 2 then return NULL
  fi;
  m:= PrimitiveRoot(n, ith=Totient(Totient(n)));
  if isprime(m) then NULL else m fi
end proc:
f(1):= 0:map(f, [$1..300]); # Robert Israel, Dec 01 2024

Offset changed by Robert Israel, Dec 01 2024

A175594 Numbers having no primitive root.

Original entry on oeis.org

0, 8, 12, 15, 16, 20, 21, 24, 28, 30, 32, 33, 35, 36, 39, 40, 42, 44, 45, 48, 51, 52, 55, 56, 57, 60, 63, 64, 65, 66, 68, 69, 70, 72, 75, 76, 77, 78, 80, 84, 85, 87, 88, 90, 91, 92, 93, 95, 96, 99, 100, 102, 104, 105, 108, 110, 111, 112, 114, 115, 116, 117, 119, 120, 123

Offset: 1

Vladislav-Stepan Malakhovsky and Juri-Stepan Gerasimov, Jul 20 2010

nonn

Union of {0} and A033949.

Numbers n such that A046145(n)=0 except n=1.

Prepend[Select[Range[2, 123], Not[IntegerQ[PrimitiveRoot[#]]] &], 0] (* Alonso del Arte, Dec 12 2011 *)

from sympy import primepi, integer_nthroot
def A175594(n):
    if n==1: return 0
    def f(x): return int(n+(x>=2)+(x>=4)+sum(primepi(integer_nthroot(x,k)[0])-1 for k in range(1,x.bit_length()))+sum(primepi(integer_nthroot(x>>1,k)[0])-1 for k in range(1,x.bit_length()-1)))
    m, k = n, f(n)
    while m != k: m, k = k, f(k)
    return m # Chai Wah Wu, Feb 25 2025

Corrected by R. J. Mathar, Oct 15 2011

Corrected by Arkadiusz Wesolowski, Sep 06 2012

A214158 Smallest number with n as least nonnegative primitive root, or 0 if no such number exists.

Original entry on oeis.org

1, 2, 3, 4, 0, 6, 41, 22, 0, 0, 313, 118, 4111, 457, 1031, 439, 0, 262, 53173, 191, 107227, 362, 3361, 842, 533821, 0, 12391, 0, 133321, 2906, 124153, 2042, 0, 3062, 48889, 2342, 0, 7754, 55441, 19322, 1373989, 3622, 2494381, 16022, 71761, 613034, 273001, 64682, 823766851, 0, 23126821, 115982, 129361, 29642

Offset: 0

Arkadiusz Wesolowski, Jul 05 2012

nonn

a(A001597(n)) = 0 for n > 1.

			a(7) = 22, since 22 has 7 as smallest positive primitive root and no number < 22 has 7 as smallest positive primitive root.

G. L. Honaker, Jr. and Chris Caldwell, Prime Curios! 313
Eric Weisstein's World of Mathematics, Primitive Root
Robert G. Wilson v, Table of n, a(n) for n = 0..205 (contains -1 where a term has not yet been found)

Cf. A046145, A046147, A023048.

lst2 = {}; r = 47; smallestPrimitiveRoot[n_ /; n <= 1] = 0; smallestPrimitiveRoot[n_] := Block[{pr = PrimitiveRoot[n], g}, If[! NumericQ[pr], g = 0, g = 1; While[g <= pr, If[CoprimeQ[g, n] && MultiplicativeOrder[g, n] == EulerPhi[n], Break[]]; g++]]; g]; lst1 = Union[Flatten@Table[n^i, {i, 2, Log[2, r]}, {n, 2, r^(1/i)}]]; Do[n = 2; If[MemberQ[lst1, l], AppendTo[lst2, 0], While[True, If[smallestPrimitiveRoot[n] == l, AppendTo[lst2, n]; Break[]]; n++]], {l, r}]; Prepend[lst2, 1] (* Most of the code is from Jean-François Alcover *)

A247176 Largest number of maximal order mod n.

Original entry on oeis.org

0, 1, 2, 3, 3, 5, 5, 7, 5, 7, 8, 11, 11, 5, 13, 13, 14, 11, 15, 17, 19, 19, 21, 23, 23, 19, 23, 23, 27, 23, 24, 29, 29, 31, 33, 31, 35, 33, 37, 37, 35, 31, 34, 41, 43, 43, 45, 43, 47, 47, 46, 45, 51, 47, 53, 53, 53, 55, 56, 53, 59, 55, 61, 61, 63, 61, 63, 65, 67, 67, 69, 67

Offset: 1

Eric Chen, Nov 29 2014

			a(18) = 11 because the largest possible order mod 18 is 6, and because 16, 15, 14, and 12 are not coprime to 18, and the orders of 17 and 13 to mod 18 are 2 and 3, not the largest possible order, and the order of 11 to mod 18 is 6, so a(18) = 11.

Eric Chen, Table of n, a(n) for n = 1..1000

Cf. A002322 (orders), same as A046146 for n with primitive roots, A071894 (for primes).

Cf. A111076, A111725, A046145, A046144, A001918, A008330.

prms={}; f[n_] = Block[If[MultiplicativeOrder[p, n]=CarmichaelLambda[n], Join[prms, p]]; prms[-1]]; Array[f, 128]

carmichaellambda(n)=lcm(znstar(n)[2]);
for(i=1, 128, p=0; for(q=1, i-1, if(gcd(q, i)==1&&znorder(Mod(q, i))==carmichaellambda(i), p=q)); print1(p", "))

a(68) corrected by Eric Chen, Jun 01 2015

A158248 Composite numbers with primitive root 10.

Original entry on oeis.org

49, 289, 343, 361, 529, 841, 2209, 2401, 3481, 3721, 4913, 6859, 9409, 11881, 12167, 12769, 16807, 17161, 22201, 24389, 27889, 32041, 32761, 37249, 49729, 52441, 54289, 66049, 69169, 72361, 83521, 97969

Offset: 1

Robert Hutchins, Mar 15 2009

Previous name was: Numbers m whose reciprocal generates a repeating decimal fraction with period phi(m) and m/2 < phi(m) < m-1.
All terms are proper powers of full reptend primes (A001913).
This sequence does not contain every proper power of every term in A001913, for example, A001913 has 487 as its 26th term, but since 10 is not a primitive root of 487^2, 487^2 is not a term of this sequence. - Robert Hutchins, Oct 14 2021
A shorter description appears to be "Composite numbers with primitive root 10". - Arkadiusz Wesolowski, Jul 04 2012 (The two definitions certainly produce the same terms up through 83521. - N. J. A. Sloane, Jul 05 2012)

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

Cf. A007732, A001913, A046145, A046146.
Subsequence of A244623.
Subsequence of A167797.
Cf. A108989 (for base 2), A346316 (for base 6).

select(n -> not isprime(n) and numtheory:-primroot(9,n) = 10,[$2..10000]);
# N. J. A. Sloane, Jul 05 2012

Select[Range[10^5], GCD[10, #] == 1 && #/2 < MultiplicativeOrder[10, #] < # - 1 &] (* Ray Chandler, Oct 17 2012 *)

More terms from Robert Hutchins, Mar 21 2009
Entry revised by N. J. A. Sloane, Jul 05 2012
New name (using comment by Arkadiusz Wesolowski) from Joerg Arndt, Nov 22 2021

A175593 Numbers k such that 2k has no primitive root but 2k-1 and 2*k+1 both have primitive roots.

Original entry on oeis.org

4, 6, 12, 14, 15, 21, 24, 30, 36, 40, 51, 54, 63, 69, 75, 84, 90, 96, 99, 114, 120, 135, 141, 156, 174, 180, 210, 216, 231, 261, 285, 300, 309, 321, 330, 364, 405, 411, 414, 420, 429, 441, 510, 516, 525, 531, 546, 576, 615, 639, 645, 651, 660, 684, 714, 726, 741

Offset: 1

Vladislav-Stepan Malakhovsky and Juri-Stepan Gerasimov, Jul 20 2010

nonn

			4 is in the sequence because 8 is not in A033948 but 7 and 9 are.

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

Cf. A033948, A046145.

noprQ[n_] := ! IntegerQ @ PrimitiveRoot[n]; q[n_] := noprQ /@ (2*n + {-1, 0, 1}) == {False, True, False}; Select[Range[2, 1000], q] (* Amiram Eldar, Oct 03 2021 *)

{k: A046145(2*k)=0 and A046145(2*k-1)>0 and A046145(2*k+1)>0}.

cp's OEIS Frontend

A285512 a(n) = smallest integer m>0 such that the positive integers not exceeding m and coprime to n generate the multiplicative group U(Z/nZ).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A206550 Smallest positive primitive roots Modd n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A103336 Numbers whose largest primitive root (A046146) is not prime.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A103337 Smallest primitive root of numbers in sequence A103335.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Extensions

A103338 Largest primitive root of numbers in sequence A103336.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Extensions

A175594 Numbers having no primitive root.

Views

Author

Keywords

Comments

Programs

Mathematica

Python

Extensions

A214158 Smallest number with n as least nonnegative primitive root, or 0 if no such number exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A247176 Largest number of maximal order mod n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A158248 Composite numbers with primitive root 10.

Views

Author

Keywords

Comments

A175593 Numbers k such that 2k has no primitive root but 2k-1 and 2*k+1 both have primitive roots.