A001918 -id:A001918 - cp's OEIS frontend

A047936 Primes whose smallest positive primitive root (A001918) is not prime.

2, 41, 109, 151, 229, 251, 271, 313, 337, 367, 409, 439, 733, 761, 971, 991, 1021, 1031, 1069, 1289, 1297, 1303, 1429, 1471, 1489, 1759, 1783, 1789, 1811, 1871, 1873, 1879, 2137, 2411, 2441, 2551, 2749, 2791, 2971, 3001, 3061, 3079, 3109, 3221, 3229

Offset: 1

Felice Russo

Subsequence of A222717 = primes whose smallest positive quadratic nonresidue is not a primitive root. (Proof. If p is not in A222717, then the smallest positive quadratic nonresidue of p is a primitive root g. Since the smallest positive quadratic nonresidue is always a prime, g is prime. But since all primitive roots are quadratic nonresidues, g is the smallest positive primitive root of p. Hence p is not in A047936.) - Jonathan Sondow, Mar 13 2013.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Index entries for primes by primitive root

Cf. A222717, A223036.

lst={}; Do[p=Prime[n]; pr=PrimitiveRoot[p]; If[pr>1&&!PrimeQ[pr], AppendTo[lst, p]], {n, 7!}]; lst (* Vladimir Joseph Stephan Orlovsky, Oct 24 2009 *)
Select[Prime[Range[500]],!PrimeQ[PrimitiveRoot[#]]&] (* Harvey P. Dale, Oct 24 2011 *)

select(p->!isprime(lift(znprimroot(p))),primes(999)) \\ reverse order of arguments if using an old version of GP
\\ Charles R Greathouse IV, Oct 24 2011

More terms from James Sellers, Dec 22 1999

A101051 Numbers m such that Sum_{p prime|m} p^r(p) = m, where r(p) is the least positive primitive root of p (A001918).

Original entry on oeis.org

2, 9, 25, 121, 132, 169, 343, 361, 841, 1369, 2809, 3481, 3721, 4489, 4913, 6889, 10201, 11449, 16371, 17161, 19321, 22201, 26569, 29791, 29929, 32041, 32761, 38809, 44521, 51529, 72361, 79507, 85849, 100489, 120409, 121801, 139129, 143641

Offset: 1

Sven Simon, Nov 28 2004

nonn

Most terms m of the sequence have k = omega(m) = 1, only 132 and 16371 with k=3 are found. Further searches did not find any more terms with k >= 3. k has to be odd in any case, this can be easily seen by looking at the parity of the prime factors. Perhaps someone with a stronger computer can find more numbers with k>1, if there are any. [There are no other terms that are not prime powers among the first 1000 terms. - Amiram Eldar, Sep 25 2021]

			16371 = 3^2 * 17 * 107 = 3^2 + 17^3 + 107^2.

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

Cf. A001918.

f[p_, e_] := p^PrimitiveRoot[p]; q[n_] := Plus @@ f @@@ FactorInteger[n] == n; Select[Range[2, 10^5], q] (* Amiram Eldar, Sep 25 2021 *)

Shorter name from Amiram Eldar, Sep 25 2021

A356856 Primes p such that the least positive primitive root of p (A001918) divides p-1.

Original entry on oeis.org

2, 3, 5, 7, 11, 13, 19, 29, 31, 37, 43, 53, 59, 61, 67, 71, 79, 83, 101, 107, 109, 127, 131, 139, 149, 151, 163, 173, 179, 181, 191, 197, 199, 211, 223, 227, 229, 239, 269, 271, 283, 293, 317, 331, 347, 349, 367, 373, 379, 389, 419, 421, 443, 461, 463, 467, 487

Offset: 1

Giorgos Kalogeropoulos, Aug 31 2022

nonn

If Artin's conjecture is true then this sequence is infinite because it contains all primes with primitive root 2.

Conjecture: This sequence has density ~0.548 in the prime numbers.

			71 is a term because the least primitive root of the prime number 71 is 7 and 7 divides 71 - 1 = 70.

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

Cf. A006093, A001918.

filter:= proc(p) local r;
  if not isprime(p) then return false fi;
  r:= NumberTheory:-PrimitiveRoot(p);
  p-1 mod r = 0
end proc:
select(filter, [2,seq(i,i=3..1000,2)]); # Robert Israel, Aug 31 2023

Select[Prime@Range@100, Mod[# - 1, PrimitiveRoot@#] == 0 &]

A060749 Triangle in which n-th row lists all primitive roots modulo the n-th prime.

Original entry on oeis.org

1, 2, 2, 3, 3, 5, 2, 6, 7, 8, 2, 6, 7, 11, 3, 5, 6, 7, 10, 11, 12, 14, 2, 3, 10, 13, 14, 15, 5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27, 3, 11, 12, 13, 17, 21, 22, 24, 2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35, 6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35

Offset: 1

N. J. A. Sloane, Apr 23 2001

Row n has A008330(n) terms. - Alford Arnold, Aug 22 2004

			The triangle a(n,k) begins (second column pr(n) is here prime(n)):
n  pr(n)\k 1  2  3  4  5  6  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27...
1    2     1
2    3     2
3    5     2  3
4    7     3  5
5   11     2  6  7  8
6   13     2  6  7 11
7   17     3  5  6  7 10 11 12 14
8   19     2  3 10 13 14 15
9   23     5  7 10 11 14 15 17 19 20 21
10  29     2  3  8 10 11 14 15 18 19 21 26 27
11  31     3 11 12 13 17 21 22 24
12  37     2  5 13 15 17 18 19 20 22 24 32 35
13  41     6  7 11 12 13 15 17 19 22 24 26 28 29 30 34 35
14  43     3  5 12 18 19 20 26 28 29 30 33 34
15  47     5 10 11 13 15 19 20 22 23 26 29 30 31 33 35 38 39 40 41 43 44 45
16  53     2  3  5  8 12 14 18 19 20 21 22 26 27 31 32 33 34 35 39 41 45 48 50 51
17  59     2  6  8 10 11 13 14 18 23 24 30 31 32 33 34 37 38 39 40 42 43 44 47 50 52 54 55 56
18  61     2  6  7 10 17 18 26 30 31 35 43 44 51 54 55 59
19  67     2  7 11 12 13 18 20 28 31 32 34 41 44 46 48 50 51 57 61 63
20  71     7 11 13 21 22 28 31 33 35 42 44 47 52 53 55 56 59 61 62 63 65 67 68 69
---------------------------------------------------------------------------------
... reformatted and extended. - _Wolfdieter Lang_, May 18 2014

R. Osborn, Tables of All Primitive Roots of Odd Primes Less Than 1000, Univ. Texas Press, 1961.

T. D. Noe, Table of n, a(n) for n = 1..9076 (first 100 rows)
C. W. Curtis, Pioneers of Representation Theory, Amer. Math. Soc., 1999; see p. 3.

Diagonals give A001918, A071894.

Cf. A008330, A046147.

prQ[p_, a_] := Block[{d = Most@Divisors[p - 1]}, If[ GCD[p, a] == 1, FreeQ[ PowerMod[a, d, p], 1], False]]; f[n_] := Select[Range@n, prQ[n, # ] &]; Table[ f[Prime[n]], {n, 13}] // Flatten (* Robert G. Wilson v, Dec 17 2005 *)
primRoots[p_] := (g = PrimitiveRoot[p]; goodOddIntegers = Select[Range[1, p-1, 2], CoprimeQ[#, p-1]&]; allPrimRoots = PowerMod[g, #, p]& /@ goodOddIntegers; Sort[allPrimRoots]); primRoots /@ Prime[Range[50]] // Flatten (* Jean-François Alcover, Nov 12 2014, after Peter Luschny *)
roots[n_] := PrimitiveRootList[Prime[n]]; Array[roots, 50] // Flatten (* Jean-François Alcover, Feb 01 2016 *)

ar(n)=local(r,p,pr,j);p=prime(n);r=vector(eulerphi(p-1));pr=znprimroot(p);for(i=1,p-1,if(gcd(i,p-1)==1,r[j++]=lift(pr^i)));vecsort(r) \\ Franklin T. Adams-Watters, Jan 22 2012

def primroots(p):
    g = primitive_root(p)
    znorder = p - 1
    is_coprime = lambda x: gcd(x, znorder) == 1
    good_odd_integers = filter(is_coprime, [1..p-1, step=2])
    all_primroots = [power_mod(g, k, p) for k in good_odd_integers]
    all_primroots.sort()
    return all_primroots # Minh Van Nguyen, Functional Programming for Mathematicians, Tutorial at sagemath.org
for p in primes(1, 50) : print(primroots(p)) # Peter Luschny, Jun 08 2011

More terms from Alford Arnold, Aug 22 2004
More terms from Paul Stoeber (pstoeber(AT)uni-potsdam.de), Oct 08 2005
Terms 26, 28, 29, 30, 34, 35 added; completion of row n=13. - Wolfdieter Lang, May 18 2014

A061323 Primes with 10 as smallest positive primitive root.

Original entry on oeis.org

313, 337, 1021, 1297, 1783, 1873, 2137, 2971, 3221, 3313, 4051, 4339, 5233, 5531, 5743, 6073, 6301, 6337, 6553, 6793, 7177, 7753, 8233, 9109, 9697, 9829, 9931, 10273, 10781, 11059, 11149, 11257, 11617, 11941, 11971, 12143, 12457, 12577

Offset: 1

Klaus Brockhaus, Apr 24 2001

nonn

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

Cf. A001918, A001126, A001913.

Prime[ Select[ Range[2000], PrimitiveRoot[ Prime[ # ] ] == 10 & ] ]
Select[ Prime@Range@1510, PrimitiveRoot@# == 10 &] (* Robert G. Wilson v, May 11 2001 *)

is(n)=n>9 && isprime(n) && znorder(Mod(2,n))Charles R Greathouse IV, Apr 24 2015

A061335 Primes with 23 as smallest positive primitive root.

Original entry on oeis.org

2161, 8761, 10559, 12479, 12911, 13729, 15601, 18121, 19009, 21787, 31249, 35281, 37321, 42841, 43201, 49921, 50951, 51239, 52711, 53231, 67489, 70249, 79801, 88919, 90121, 90289, 91393, 97919, 106129, 106391, 106681, 107881, 108529, 115201, 123191, 126311

Offset: 1

Klaus Brockhaus, Apr 25 2001

nonn

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

Cf. A001918, A001126, A019350.

Prime[ Select[ Range[12100], PrimitiveRoot[ Prime[ # ] ] == 23 & ] ]
Select[ Prime@Range@10880, PrimitiveRoot@# == 23 &] (* Robert G. Wilson v, May 11 2001 *)

is(n)=my(v=[2, 3, 5, 7, 11, 13, 17, 19, 6, 10, 12, 14, 15, 18, 20, 21, 22]); if(!isprime(n) || n<99, return(0)); for(i=1,#v, if(znorder(Mod(v[i], n))==n-1, return(0))); znorder(Mod(23,n))==n-1 \\ Charles R Greathouse IV, Apr 27 2015

A061730 Primes with 24 as smallest positive primitive root.

Original entry on oeis.org

533821, 567631, 672181, 843781, 1035301, 1512421, 1929061, 2260501, 2839621, 2894431, 2896741, 4466221, 5428231, 5970511, 6170911, 9340501, 9730711, 9920821, 10635661, 10684759, 10720711, 10870471, 11425261, 11591581

Offset: 1

Klaus Brockhaus, May 06 2001

nonn

Vincenzo Librandi, Table of n, a(n) for n = 1..225

Cf. A001918, A001126, A019351.

Prime[ Select[ Range[ 10^6], PrimitiveRoot[ Prime[ # ] ] == 24 & ] ]
(* or *)
Select[ Prime@Range@1000000, PrimitiveRoot@# == 24 &] (* Robert G. Wilson v, May 11 2001 *)

is(n)=if(n<9||!isprime(n), return(0)); for(k=2,23, if(znorder(Mod(k,n))==n-1, return(0))); znorder(Mod(24,n))==n-1 \\ Charles R Greathouse IV, Apr 28 2015

More terms from Robert G. Wilson v, May 11 2001

A061741 Primes with 39 as smallest positive primitive root.

Original entry on oeis.org

166031, 264961, 325249, 388081, 450071, 462841, 543601, 735271, 816649, 823201, 915049, 1063561, 1155151, 1414081, 1415929, 1554169, 1704271, 1884121, 1952449, 2181271, 2215921, 2290831, 2477521, 2499421, 2514961, 2585647, 2633689

Offset: 1

Klaus Brockhaus, May 06 2001

nonn

Vincenzo Librandi, Table of n, a(n) for n = 1..660

Cf. A001918, A019364, A001122-A001126, A061323-A061335, A061730-A061741, A114657-A114686.

Select[ Prime@Range@221000, PrimitiveRoot@# == 39 &] (* Robert G. Wilson v, May 11 2001 *)

is(n)=if(n<9||!isprime(n), return(0)); for(k=2,38,if(znorder(Mod(k,n))==n-1, return(0))); znorder(Mod(39,n))==n-1 \\ Charles R Greathouse IV, Apr 28 2015

More terms from Robert G. Wilson v, May 11 2001 and Dec 21 2005

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

cp's OEIS Frontend

A047936 Primes whose smallest positive primitive root (A001918) is not prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A101051 Numbers m such that Sum_{p prime|m} p^r(p) = m, where r(p) is the least positive primitive root of p (A001918).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A356856 Primes p such that the least positive primitive root of p (A001918) divides p-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A060749 Triangle in which n-th row lists all primitive roots modulo the n-th prime.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Extensions

A061323 Primes with 10 as smallest positive primitive root.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A061335 Primes with 23 as smallest positive primitive root.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A061730 Primes with 24 as smallest positive primitive root.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A061741 Primes with 39 as smallest positive primitive root.

Views

Author

Keywords