A002233 -id:A002233 - cp's OEIS frontend

A001918 Least positive primitive root of n-th prime.

1, 2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 6, 3, 5, 2, 2, 2, 2, 7, 5, 3, 2, 3, 5, 2, 5, 2, 6, 3, 3, 2, 3, 2, 2, 6, 5, 2, 5, 2, 2, 2, 19, 5, 2, 3, 2, 3, 2, 6, 3, 7, 7, 6, 3, 5, 2, 6, 5, 3, 3, 2, 5, 17, 10, 2, 3, 10, 2, 2, 3, 7, 6, 2, 2, 5, 2, 5, 3, 21, 2, 2, 7, 5, 15, 2, 3, 13, 2, 3, 2, 13, 3, 2, 7, 5, 2, 3, 2, 2, 2, 2, 2, 3

Offset: 1

N. J. A. Sloane

If k is a primitive root of p=4m+1, then p-k is too. If k is a primitive root of p=4m+3, then p-k isn't, but has order 2m+1. - Jon Perry, Sep 07 2014

			modulo 7: 3^6=1, 3^2=2, 3^7=3, 3^4=4, 3^5=5, 3^3=6, 7=prime(4), 3=a(4).

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 864.
T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 213.
CRC Handbook of Combinatorial Designs, 1996, p. 615.
P. Fan and M. Darnell, Sequence Design for Communications Applications, Wiley, NY, 1996, Table A.1.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, th. 111.
Hua Loo Keng, Introduction To Number Theory, 'Table of least primitive roots for primes less than 50000', pp. 52-6, Springer NY 1982.
R. Osborn, Tables of All Primitive Roots of Odd Primes Less Than 1000, Univ. Texas Press, 1961.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 20.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Loo-keng Hua, On the least primitive root of a prime, Bull. Amer. Math. Soc. 48 (1942), 726-730.
K. Matthews, Finding the least primitive root (mod p), p an odd prime
Jorma K. Merikoski, Pentti Haukkanen, and Timo Tossavainen, The congruence x^n = -a^n (mod m): Solvability and related OEIS sequences, Notes. Num. Theor. Disc. Math. (2024) Vol. 30, No. 3, 516-529. See p. 519.
T. Oliveira e Silva, Least primitive root of prime numbers.
Eric Weisstein's World of Mathematics, Primitive Root.

A column of A060749. Cf. A002233.

A001918 := proc(n)
        numtheory[primroot](ithprime(n)) ;
end proc:

Table[PrimitiveRoot@Prime@n, {n, 101}] (* Robert G. Wilson v, Dec 15 2005 *)
PrimitiveRoot[Prime[Range[110]]] (* Harvey P. Dale, Jan 13 2013 *)

for(x=1, 1000, print1(lift(znprimroot(prime(x))), ", "))

from sympy import prime
from sympy.ntheory.residue_ntheory import primitive_root
def A001918(n): return primitive_root(prime(n)) # Chai Wah Wu, Sep 13 2022

[primitive_root(p) for p in primes(570)] # Zerinvary Lajos, May 24 2009

A046144 Number of primitive roots modulo n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 0, 2, 2, 4, 0, 4, 2, 0, 0, 8, 2, 6, 0, 0, 4, 10, 0, 8, 4, 6, 0, 12, 0, 8, 0, 0, 8, 0, 0, 12, 6, 0, 0, 16, 0, 12, 0, 0, 10, 22, 0, 12, 8, 0, 0, 24, 6, 0, 0, 0, 12, 28, 0, 16, 8, 0, 0, 0, 0, 20, 0, 0, 0, 24, 0, 24, 12, 0, 0, 0, 0, 24, 0, 18, 16, 40, 0, 0, 12, 0, 0, 40, 0, 0

Offset: 1

Eric W. Weisstein

nonn

T. D. Noe, Table of n, a(n) for n = 1..10000
S. R. Finch, Idempotents and Nilpotents Modulo n, arXiv:math/0605019 [math.NT], 2006-2017.
Eric Weisstein's World of Mathematics, Primitive Root.

Cf. A001918, A010554, A033949, A046145, A046146, A008330, A002233, A071894, A219027.

A046144 := proc(n)
    local a,eulphi,m;
    if n = 1 then
        return 1;
    end if;
    eulphi := numtheory[phi](n) ;
    a := 0 ;
    for m from 0 to n-1 do
        if numtheory[order](m,n) = eulphi then
            a := a + 1 ;
        end if;
    end do:
    a;
end proc: # R. J. Mathar, Jan 12 2016

Prepend[ Table[ If[ IntegerQ[ PrimitiveRoot[n]] , EulerPhi[ EulerPhi[n]], 0], {n, 2, 91}],1] (* Jean-François Alcover, Sep 13 2011 *)

for(i=1, 100, p=0; for(q=1, i, if(gcd(q,i)==1 && znorder(Mod(q,i)) == eulerphi(i), p++)); print1(p, ", ")) /* V. Raman, Nov 22 2012 */

a(n) = my(s=znstar(n)); if(#(s.cyc)>1, 0, eulerphi(s.no)) \\ Jeppe Stig Nielsen, Oct 18 2019

use ntheory ":all"; my @A = map { !defined znprimroot($) ? 0 : euler_phi(euler_phi($)); } 0..10000; say "$ $A[$]" for 1..$#A; # Dana Jacobsen, Apr 28 2017

a(n) is equal to A010554(n) unless n is a term of A033949, in which case a(n)=0.

A046145 Smallest primitive root modulo n, or 0 if no root exists.

Original entry on oeis.org

0, 0, 1, 2, 3, 2, 5, 3, 0, 2, 3, 2, 0, 2, 3, 0, 0, 3, 5, 2, 0, 0, 7, 5, 0, 2, 7, 2, 0, 2, 0, 3, 0, 0, 3, 0, 0, 2, 3, 0, 0, 6, 0, 3, 0, 0, 5, 5, 0, 3, 3, 0, 0, 2, 5, 0, 0, 0, 3, 2, 0, 2, 3, 0, 0, 0, 0, 2, 0, 0, 0, 7, 0, 5, 5, 0, 0, 0, 0, 3, 0, 2, 7, 2, 0, 0, 3, 0, 0, 3, 0, 0, 0, 0, 5, 0, 0, 5, 3, 0, 0

Offset: 0

Eric W. Weisstein

The value 0 at index 0 says 0 has no primitive roots, but the 0 at index 1 says 1 has a primitive root of 0, the only real 0 in the sequence.

a(n) is nonzero if and only if n is 2, 4, or of the form p^k, or 2*p^k where p is an odd prime and k>0. - Tom Edgar, Jun 02 2014

T. D. Noe, Table of n, a(n) for n = 0..10000
Pēteris K. Siliņš, Cross ratios for finite field geometries, Bachelor's Thesis, Univ. Groningen (Netherlands, 2024). See p. 17.
Eric Weisstein's World of Mathematics, Primitive Root.

Cf. A001918, A046144, A046146, A002233, A071894, A219027, A008330, A010554, A111076, A285512, A285513, A285514.

A046145 := proc(n)
  if n <=1 then
    0;
  else
    pr := numtheory[primroot](n) ;
    if pr = FAIL then
       return 0 ;
    else
       return pr ;
    end if;
  end if;
end proc:
seq(A046145(n),n=0..110) ;  # R. J. Mathar, Jul 08 2010

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]; smallestPrimitiveRoot /@ Range[0, 100] (* Jean-François Alcover, Feb 15 2012 *)
f[n_] := Block[{pr = PrimitiveRootList[n]}, If[pr == {}, 0, pr[[1]]]]; Array[f, 105, 0] (* v10.0 Robert G. Wilson v, Nov 04 2014 *)

{ A046145(n) = for(q=1,n-1, if(gcd(q,n)==1 && znorder(Mod(q,n))==eulerphi(n), return(q);)); 0; } /* V. Raman, Nov 22 2012, edited by Max Alekseyev, Apr 20 2017 */

use ntheory ":all"; say "$ ", znprimroot($) || 0  for 0..100; # Dana Jacobsen, Mar 16 2017

Initial terms corrected by Harry J. Smith, Jan 27 2005

A046146 Largest primitive root modulo n, or 0 if no root exists.

Original entry on oeis.org

0, 0, 1, 2, 3, 3, 5, 5, 0, 5, 7, 8, 0, 11, 5, 0, 0, 14, 11, 15, 0, 0, 19, 21, 0, 23, 19, 23, 0, 27, 0, 24, 0, 0, 31, 0, 0, 35, 33, 0, 0, 35, 0, 34, 0, 0, 43, 45, 0, 47, 47, 0, 0, 51, 47, 0, 0, 0, 55, 56, 0, 59, 55, 0, 0, 0, 0, 63, 0, 0, 0, 69, 0, 68, 69, 0, 0, 0, 0, 77, 0, 77, 75, 80, 0, 0

Offset: 0

Eric W. Weisstein

nonn

The value 0 at index 0 says 0 has no primitive roots, but the 0 at index 1 says 1 has a primitive root of 0, the only real 0 in the sequence. - Initial terms corrected by Harry J. Smith, Jan 27 2005

a(n) is nonzero if and only if n is 2, 4, or of the form p^k, or 2*p^k where p is an odd prime and k>0. - Tom Edgar, Jun 02 2014

T. D. Noe, Table of n, a(n) for n = 0..10000
Eric Weisstein's World of Mathematics, Primitive Root.

Cf. A001918, A046144, A046145, A002233, A071894, A219027, A008330, A010554.

f[n_] := Block[{pr = PrimitiveRootList[n]}, If[pr == {}, 0, pr[[-1]]]]; Array[f, 86, 0] (* Robert G. Wilson v, Nov 03 2014 *)

for(i=0,100,p=0;for(q=1,i-1,if(gcd(q,i)==1&&znorder(Mod(q,i))==eulerphi(i),p=q));print1(p",")) /* V. Raman, Nov 22 2012 */

Initial terms corrected by Harry J. Smith, Jan 27 2005

A122028 Least positive prime primitive root of n-th prime.

Original entry on oeis.org

3, 2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 7, 3, 5, 2, 2, 2, 2, 7, 5, 3, 2, 3, 5, 2, 5, 2, 11, 3, 3, 2, 3, 2, 2, 7, 5, 2, 5, 2, 2, 2, 19, 5, 2, 3, 2, 3, 2, 7, 3, 7, 7, 11, 3, 5, 2, 43, 5, 3, 3, 2, 5, 17, 17, 2, 3, 19, 2, 2, 3, 7, 11, 2, 2, 5, 2, 5, 3, 29, 2, 2, 7, 5, 17, 2, 3, 13, 2, 3, 2, 13, 3, 2, 7, 5, 2, 3, 2, 2, 2

Offset: 1

N. J. A. Sloane and Klaus Brockhaus, Sep 13 2006

A. E. Western and J. C. P. Miller, Tables of Indices and Primitive Roots. Royal Society Mathematical Tables, Vol. 9, Cambridge Univ. Press, 1968, p. 2.

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A002233 (least prime primitive root).

f:= proc(n) local p,q;
p:= ithprime(n);
q:= 2:
while numtheory:-order(q,p) <> p-1 do q:= nextprime(q) od:
q
end proc:
map(f, [$1..100]); # Robert Israel, Jan 16 2017

a[1] = 3; a[n_] := (p = Prime[n]; Select[Range[p], PrimeQ[#] && MultiplicativeOrder[#, p] == EulerPhi[p] &, 1]) // First; Table[a[n], {n, 100}]   (* Jean-François Alcover, Mar 30 2011 *)
a[1] = 3; a[n_] := SelectFirst[ PrimitiveRootList[ Prime[n]], PrimeQ]; Array[a, 101] (* Jean-François Alcover, Sep 28 2016 *)

a(n) = A002233(n) for n>1. - Jonathan Sondow, May 18 2017

A138305 Irregular triangle of prime primitive roots of prime(n).

Original entry on oeis.org

2, 2, 3, 3, 5, 2, 7, 2, 7, 11, 3, 5, 7, 11, 2, 3, 13, 5, 7, 11, 17, 19, 2, 3, 11, 19, 3, 11, 13, 17, 2, 5, 13, 17, 19, 7, 11, 13, 17, 19, 29, 3, 5, 19, 29, 5, 11, 13, 19, 23, 29, 31, 41, 43, 2, 3, 5, 19, 31, 41, 2, 11, 13, 23, 31, 37, 43, 47, 2, 7, 17, 31, 43, 59, 2, 7, 11, 13, 31, 41, 61, 7

Offset: 2

T. D. Noe, Mar 14 2008

The length of row n is A138304(n).

			2;
2,3;
3,5;
2,7;
2,7,11;
3,5,7,11;

T. D. Noe, Rows n=2..100 of triangle, flattened

Cf. A002233 (least prime primitive root), A060749 (triangle of primitive roots of primes).

Flatten[Table[p=Prime[n]; Select[Prime[Range[n-1]], MultiplicativeOrder[ #,p]==p-1&], {n,100}]]

A084739 Let p = n-th prime, then a(n) = smallest prime having p as its least prime primitive root.

Original entry on oeis.org

3, 7, 23, 41, 109, 457, 311, 191, 2137, 409, 1021, 1031, 1811, 271, 14293, 2791, 55441, 35911, 57991, 221101, 23911, 11971, 110881, 103091, 71761, 513991, 290041, 31771, 448141, 2447761, 674701, 3248701, 2831011, 690541, 190321, 2080597, 4076641

Offset: 1

N. J. A. Sloane, Jul 03 2003

Smallest prime(m) such that A002233(m) = prime(n). (Corrected by Jonathan Sondow, Feb 02 2013)

N. J. A. Sloane, Table of n, a(n) for n=1..97 (from the web page of Tomás Oliveira e Silva)
Tomás Oliveira e Silva, Least primitive root of prime numbers
A. Paszkiewicz and A. Schinzel, On the least prime primitive root modulo a prime, Math. Comp. 71 (2002), no. 239, 1307-1321.

Cf. A084735, A001918, A079061. For records see A133434.

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com) and Don Reble, Jul 03 2003

A223942 Least prime q such that (x^{p_n}-1)/(x-1) is irreducible modulo q, where p_n is the n-th prime.

Original entry on oeis.org

2, 2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 7, 3, 5, 2, 2, 2, 2, 7, 5, 3, 2, 3, 5, 2, 5, 2, 11, 3, 3, 2, 3, 2, 2, 7, 5, 2, 5, 2, 2, 2, 19, 5, 2, 3, 2, 3, 2, 7, 3, 7, 7, 11, 3, 5, 2, 43, 5, 3

Offset: 1

Zhi-Wei Sun, Mar 29 2013

nonn

It is well known that (x^{p^n}-1)/(x^{p^{n-1}}-1) is irreducible over the rationals for any prime p and positive integer n.
We have the following "Reciprocity Law": For any positive integer n and primes p > 2 and q, the cyclotomic polynomial (x^{p^n}-1)/(x^{p^{n-1}}-1) is irreducible modulo q if and only if q is a primitive root modulo p^n.
This can be proved as follows: As any monic irreducible polynomial over F_q=Z/qZ of degree k divides x^{q^k}-x in the ring F_q[x], the polynomial f(x)= (x^{p^n}-1)/(x^{p^{n-1}}-1) in F_q[x] has an irreducible factor of degree k < deg f if and only if f(x) is not coprime to x^{q^k}-x for some k < p^n-p^{n-1}. Note that gcd(x^{p^n}-1,x^{q^k-1}-1) = x^{gcd(p^n,q^k-1)}-1. If p^n | q^k-1, then x^{p^n}-1 | x^{q^k}-x and hence f(x) divides x^{q^k}-x; if p^n does not divide q^k-1, then gcd(x^{p^n}-1,x^{q^k-1}-1) divides x^{p^{n-1}}-1 and hence f(x) is coprime to x^{q^k}-x. Thus, f(x) is irreducible modulo q, if and only if p^n | q^k-1 for no 0 < k < p^n-p^{n-1}, i.e., q is a primitive root modulo p^n.
By the above "Reciprocity Law" in the case n=1, we have a(k) = A002233(k) for all k > 1.
Conjecture: a(n) <= sqrt(7*p_n) for all n>0.

			  a(9)=5 since f(x)=(x^{23}-1)/(x-1) is irreducible modulo 5, but reducible modulo either of 2 and 3, for,
   f(x)==(x^{11}+x^9+x^7+x^6+x^5+x+1)
         *(x^{11}+x^{10}+x^6+x^5+x^4+x^2+1) (mod 2)
and
   f(x)==(x^{11}-x^8-x^6+x^4+x^3-x^2-x-1)
         *(x^{11}+x^{10}+x^9-x^8-x^7+x^5+x^3-1) (mod 3).

Zhi-Wei Sun, Table of n, a(n) for n = 1..450

Cf. A000040, A002233, A122028, A217785, A217788, A218465, A220072, A223934.

Do[Do[If[IrreduciblePolynomialQ[Sum[x^k,{k,0,Prime[n]-1}],Modulus->Prime[k]]==True,Print[n," ",Prime[k]];Goto[aa]],{k,1,PrimePi[Sqrt[7*Prime[n]]]}];
Print[n," ",counterexample];Label[aa];Continue,{n,1,100}]

A219429 Highest prime primitive root (less than p) for the n-th prime p. (or 0 if none exists).

Original entry on oeis.org

0, 2, 3, 5, 7, 11, 11, 13, 19, 19, 17, 19, 29, 29, 43, 41, 47, 59, 61, 67, 59, 59, 79, 83, 83, 89, 101, 103, 103, 107, 109, 127, 131, 109, 139, 109, 151, 149, 163, 131, 167, 179, 181, 167, 179, 197, 191, 173, 223, 223, 227, 227, 227, 239, 251, 257, 257

Offset: 1

V. Raman, Nov 19 2012

nonn

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

Cf. A002233 (lowest prime primitive root for the n-th prime).
Cf. A001918 (lowest primitive root for the n-th prime).
Cf. A071894 (highest primitive root (less than p) for the n-th prime p).

f:=proc(n) local p,k;
   p:= ithprime(n);
   for k from p-1 to 1 by -1 do
     if numtheory:-order(k,p) = p-1 and isprime(k) then return k fi
   od;
0
end proc;
map(f, [$1..100]); # Robert Israel, Apr 11 2021

Reap[For[p = 2, p<1000, p = NextPrime[p], s = Select[PrimitiveRootList[p], PrimeQ]; Sow[If[s == {}, 0, Last[s]]]]][[2, 1]] (* Jean-François Alcover, Sep 03 2016 *)

forprime(i=2,600,p=0;for(q=1,i-1,if(znorder(Mod(q,i))==eulerphi(i)&&isprime(q),p=q));print1(p","))

A263984 Least composite primitive root of n-th prime.

Original entry on oeis.org

9, 8, 8, 10, 6, 6, 6, 10, 10, 8, 12, 15, 6, 12, 10, 8, 6, 6, 12, 21, 14, 6, 6, 6, 10, 8, 6, 6, 6, 6, 6, 6, 6, 12, 8, 6, 6, 12, 10, 8, 6, 10, 21, 10, 8, 6, 22, 6, 6, 6, 6, 14, 14, 6, 6, 10, 8, 6, 6, 12, 12, 8, 14, 22, 10, 8, 28, 10, 6, 18

Offset: 1

Franklin T. Adams-Watters, Oct 31 2015

nonn

The only square in the sequence is a(1) = 9.

It seems nearly certain that all nonsquare composite numbers occur in this sequence.

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

Cf. A001918, A002233, A122028.

primrootQ[n_, r_] := MultiplicativeOrder[r, n] == EulerPhi[n];
a[n_] := Module[{p = Prime[n], k = 6}, While[PrimeQ[k] || GCD[k, p] != 1 || !primrootQ[p, k], k++]; k];
Array[a, 70] (* Jean-François Alcover, Oct 23 2020, after PARI code *)

isprimroot(n,r)=znorder(Mod(r,n))==eulerphi(n)
a(n)=my(p=prime(n),k=6);while(isprime(k)||gcd(k,p)!=1||!isprimroot(p,k),k++);k

cp's OEIS Frontend

A001918 Least positive primitive root of n-th prime.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Sage

A046144 Number of primitive roots modulo n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Perl

Formula

A046145 Smallest primitive root modulo n, or 0 if no root exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Perl

Extensions

A046146 Largest primitive root modulo n, or 0 if no root exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A122028 Least positive prime primitive root of n-th prime.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A138305 Irregular triangle of prime primitive roots of prime(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A084739 Let p = n-th prime, then a(n) = smallest prime having p as its least prime primitive root.

Views

Author

Keywords

Comments

Links