A071894 -id:A071894 - cp's OEIS frontend

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

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

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

A002199 Least negative primitive root of n-th prime.

Original entry on oeis.org

1, 1, 2, 2, 3, 2, 3, 4, 2, 2, 7, 2, 6, 9, 2, 2, 3, 2, 4, 2, 5, 2, 3, 3, 5, 2, 2, 3, 6, 3, 9, 3, 3, 4, 2, 5, 5, 4, 2, 2, 3, 2, 2, 5, 2, 2, 4, 9, 3, 6, 3, 2, 7, 3, 3, 2, 2, 2, 5, 3, 6, 2, 7, 2, 10, 2, 5, 10, 3, 2, 3, 2, 2, 2, 4, 2, 2, 5, 3, 21, 3, 2, 5, 5, 5, 3, 3, 13, 2, 2, 3, 2, 2, 4, 5, 2, 2, 3, 4, 2, 4, 2, 3

Offset: 1

N. J. A. Sloane

nonn

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.
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).

T. D. Noe, 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].
A. E. Western and J. C. P. Miller, Tables of Indices and Primitive Roots, Royal Society Mathematical Tables, Vol. 9, Cambridge Univ. Press, 1968 [Annotated scans of selected pages]

Cf. A060749, A001918.

Table[(k=-1;While[MultiplicativeOrder[k,p]!=p-1,k--];-k),{p,Prime@Range@100}] (* Giorgos Kalogeropoulos, Sep 28 2023 *)

a(n) = prime(n) - A071894(n). - T. D. Noe, Oct 24 2005

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

A128906 Difference between the greatest primitive root and the least primitive root of the n-th prime.

Original entry on oeis.org

0, 0, 1, 2, 6, 9, 11, 13, 16, 25, 21, 33, 29, 31, 40, 49, 54, 57, 61, 62, 63, 74, 78, 83, 87, 97, 96, 102, 97, 107, 115, 126, 131, 133, 145, 140, 147, 157, 160, 169, 174, 177, 170, 183, 193, 194, 205, 211, 222, 217, 227, 230, 227, 242, 251, 256, 265, 263, 267, 275, 274

Offset: 1

Robert G. Wilson v, Apr 21 2007

nonn

Amiram Eldar, Table of n, a(n) for n = 1..1001 (adapted to offset 1 by Sidney Cadot).

Cf. A001918, A071894.

Table[(k=p-1;While[MultiplicativeOrder[k,p]!=p-1,k--];k)-PrimitiveRoot@p,{p, Prime@Range@100}] (* Giorgos Kalogeropoulos, Sep 28 2023 *)

a(n)=my(p=prime(n));forstep(r=p-1,2,-1,if(znorder(Mod(r,p))==p-1,return(r-lift(znprimroot(p)))));
vector(66,n,a(n)) \\ Joerg Arndt, Sep 29 2023

a(n) = A071894(n) - A001918(n).

a(1)=0 inserted by Georg Fischer, Dec 11 2022

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","))

A251865 Irregular triangle read by rows in which row n lists the maximal-order elements (

Original entry on oeis.org

0, 1, 2, 3, 2, 3, 5, 3, 5, 3, 5, 7, 2, 5, 3, 7, 2, 6, 7, 8, 5, 7, 11, 2, 6, 7, 11, 3, 5, 2, 7, 8, 13, 3, 5, 11, 13, 3, 5, 6, 7, 10, 11, 12, 14, 5, 11, 2, 3, 10, 13, 14, 15, 3, 7, 13, 17, 2, 5, 10, 11, 17, 19, 7, 13, 17, 19, 5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 5, 7, 11, 13, 17, 19, 23, 2, 3, 8, 12, 13, 17, 22, 23

Offset: 1

Eric Chen, May 20 2015

Conjecture: Triangle contains all nonsquare numbers infinitely many times.
The orders of the numbers in n-th row mod n are equal to A002322(n).
First and last terms of the n-th row are A111076(n) and A247176(n).
Length of the n-th row is A111725(n).
The n-th row is the same as A046147 for n with primitive roots.

			Read by rows:
n     maximal-order elements (<n) mod n
1     0
2     1
3     2
4     3
5     2, 3
6     5
7     3, 5
8     3, 5, 7
9     2, 5
10    3, 7
11    2, 6, 7, 8
12    5, 7, 11
13    2, 6, 7, 11
14    3, 5
15    2, 7, 8, 13
16    3, 5, 11, 13
17    3, 5, 6, 7, 10, 11, 12, 14
18    5, 11
19    2, 3, 10, 13, 14, 15
20    3, 7, 13, 17
etc.

Eric Chen, First 160 rows of triangle, flattened
Eric Chen, First 1000 rows of triangle

Cf. A111076, A247176, A111725, A046147, A046145, A046146, A046144, A060749, A001918, A071894, A008330.

a[n_] := Select[Range[0, n-1], GCD[#, n] == 1 && MultiplicativeOrder[#, n] == CarmichaelLambda[n]& ]; Table[a[n], {n, 1, 36}]

c(n)=lcm((znstar(n))[2])
a(n)=for(k=0,n-1,if(gcd(k, n)==1 && znorder(Mod(k,n))==c(n), print1(k, ",")))
n=1; while(n<37, a(n); n++)

cp's OEIS Frontend

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

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

A002199 Least negative primitive root of n-th prime.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

A247176 Largest number of maximal order mod n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A128906 Difference between the greatest primitive root and the least primitive root of the n-th prime.

Views

Author

Keywords

Links

Crossrefs

Programs