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,2

Comments

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

References

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

Links

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.

Example

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

Mathematica

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

Prog

{Haskell} main=print[[n|n<-[1..p-1], let h x=if x==1 then 1 else 1+h(x*n`mod`p)in h n==p-1]|p<-let p=2:[n|(n, r)<-drop 2(zip[1..](concat[replicate(2*n+1)(toInteger n)|n<-[1..]])) and[n`mod`x/=0|x<-takeWhile(<=r)p]]in p] -- Stoeber
(PARI) 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
(Sage)
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

Crossrefs

Diagonals give A001918, A071894.

Cf. A008330, A046147.

Sequence in context: A165120 A165129 A113773 * A138305 A169897 A254309

Adjacent sequences: A060746 A060747 A060748 * A060750 A060751 A060752

Keyword

nonn,tabf,nice,easy

Author

N. J. A. Sloane, Apr 23 2001

Extensions

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

Status

approved