A046147 -id:A046147 - 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

A306252 Least primitive root mod A033948(n).

Original entry on oeis.org

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

Offset: 1

Charles Paul, Feb 01 2019

nonn

Let U(k) denote the multiplicative group mod k. a(n) = smallest generator for U(A033948(n)). - N. J. A. Sloane, Mar 10 2019

			For n=2, A033948(2) = 2, U(2) is generated by 1.
For n=14, A033948(14) = 18, and U(18) is generated by both 5 and 11; here we select the smallest generator, 5, so a(14) = 5.

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

Cf. A033948 (numbers that have a primitive root), A306253, A081888 (positions of records), A081889 (record values). First column of A046147.

0,op(subs(FAIL=NULL, map(numtheory:-primroot,[$2..1000]))); # Robert Israel, Mar 10 2019

Array[Take[PrimitiveRootList@ #, UpTo[1]] &, 210] // Flatten (* Michael De Vlieger, Feb 02 2019 *)

from math import gcd
roots = [0]
for n in range(2,140):
    # find U(n)
    un = [i for i in range(1,n) if gcd(i,n) == 1]
    # for each element in U(n), check if it's a generator
    order = len(un)
    is_cyclic = False
    for cand in un:
        is_gen = True
        run = 1
        # If it cand^x = 1 for some x < order, it's not a generator
        for _ in range(order-1):
            run = (run * cand) % n
            if run == 1:
                is_gen = False
                break
        if is_gen:
            roots.append(cand)
            is_cyclic = True
            break
print(roots)

More terms from Michael De Vlieger, Feb 02 2019
Edited by N. J. A. Sloane, Mar 10 2019
Edited by Robert Israel, Mar 10 2019

A121380 Sums of primitive roots for n (or 0 if n has no primitive roots).

Original entry on oeis.org

0, 1, 2, 3, 5, 5, 8, 0, 7, 10, 23, 0, 26, 8, 0, 0, 68, 16, 57, 0, 0, 56, 139, 0, 100, 52, 75, 0, 174, 0, 123, 0, 0, 136, 0, 0, 222, 114, 0, 0, 328, 0, 257, 0, 0, 208, 612, 0, 300, 200, 0, 0, 636, 156, 0, 0, 0, 348, 886, 0, 488, 216, 0, 0, 0, 0, 669, 0, 0, 0

Offset: 1

Ed Pegg Jr, Jul 25 2006

In Article 81 of his Disquisitiones Arithmeticae (1801), Gauss proves that the sum of all primitive roots (A001918) of a prime p, mod p, equals MoebiusMu[p-1] (A008683). "The sum of all primitive roots is either = 0 (mod p) (when p-1 is divisible by a square), or = +-1 (mod p) (when p-1 is the product of unequal prime numbers; if the number of these is even the sign is positive but if the number is odd, the sign is negative)."

			The primitive roots of 13 are 2, 6, 7, 11. Their sum is 26, or 0 (mod 13). By Gauss, 13-1=12 is thus divisible by a square number.

J. C. F. Gauss, Disquisitiones Arithmeticae, 1801.

T. D. Noe, Table of n, a(n) for n = 1..10000
Eric Weisstein, Primitive Roots.

Cf. A001918, A008683, A046147 (primitive roots of n), A088144, A088145, A123475, A222009.

primitiveRoots[n_] := If[n == 1, {}, If[n == 2, {1}, Select[Range[2, n-1], MultiplicativeOrder[#, n] == EulerPhi[n] &]]]; Table[Total[primitiveRoots[n]], {n,100}]
(* From version 10 up: *)
Table[Total @ PrimitiveRootList[n], {n, 1, 100}] (* Jean-François Alcover, Oct 31 2016 *)

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

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

A382220 Numbers k such that every primitive root mod k is prime.

Original entry on oeis.org

3, 4, 5, 6, 7, 9, 10, 14, 18, 22, 54

Offset: 1

Miles Englezou, Mar 18 2025

There are no more terms up to k = 10^8.

Is this sequence finite? Since the number of primitive roots mod k is equal to phi(phi(k)), the size of the set of primitive roots generally increases with increasing k. Coupled with the fact that there are few restrictions regarding what kind of number can be a primitive root mod k (except, for example, that no square can be a primitive root), it becomes increasingly less likely that the set of primitive roots mod k will contain only primes as k increases. Furthermore, if the odd prime factor of k is congruent to 1 mod 4, then -g is a primitive root mod k if g is, a symmetry which further decreases the likelihood that every primitive root mod k is prime for large k.

			The primitive roots mod a(n) for 1 <= n <= 11:
  3  [2]
  4  [3]
  5  [2, 3]
  6  [5]
  7  [3, 5]
  9  [2, 5]
 10  [3, 7]
 14  [3, 5]
 18  [5, 11]
 22  [7, 13, 17, 19]
 54  [5, 11, 23, 29, 41, 47]

Cf. A033948, A046147, A382224.

isok(n) = if((n==2 || n==4 || (n%4<>0 && isprimepower(n)<>0) || (n%4<>0 && n/2==floor(n/2) && isprimepower(n/2)<>0))==0, return(0), my(m=lcm(apply(f->(f[1]-1)*f[1]^(f[2]-1-(f[1]==2&&f[2]>2)), Vec(factor(n)~)))); for(k=1, n-1, if(gcd(k, n)==1 && znorder(Mod(k, n))==m && isprime(k)==0, return(0)); if(k==n-1, return(1))))

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

A306252 Least primitive root mod A033948(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Extensions

A121380 Sums of primitive roots for n (or 0 if n has no primitive roots).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A382220 Numbers k such that every primitive root mod k is prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI