A122028 -id:A122028 - cp's OEIS frontend

A002233 a(1) = 1; for n > 1, a(n) = least positive prime primitive root of n-th prime.

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

According to Section F9 in Guy's book "Unsolved Problems in Number Theory" (Springer, 2004), P. Erdős asked whether for any large prime p there is a prime q < p so that q is a primitive root modulo p. See also the comments on A223942 related to this sequence. - Zhi-Wei Sun, Mar 29 2013

For n >= 2 the Dirichlet characters modulo prime(n), {Chi_{prime n}{(r,m)}, for n >= 1, r=1..(prime(n)-1) and m = 2..prime(n)-1, are determined from those for m = a(n), i.e., Chi_{prime n}(r,a(n)) = exp(2*Pi*I*(r-1)/(prime(n)-1)) and the power sequence S(n) := {a(n)^k (mod prime(n)), k = 1..(prime(n)-2)} by the strong multiplicity of Chi as Chi_{prime n}(r,m) = (Chi_{prime n}(r,a(n)))^{pos(m,S(n))} where S(n){pos(m,S(n))} = m. For m=1 Chi is always 1. For m = prime(n) Chi is always 0. For n=1 (prime 2) the characters are 1, 0 for r = 1 and m = 1, 2, respectively. See the example for a(4) below. - _Wolfdieter Lang, Jan 19 2017

			n=4, a(4) = 3: Dirichlet characters for prime(4) = 7 from Chi_7(r,3) = exp(Pi*I*(r-1)/3) and the power sequence S(4) = [3, 2, 6, 4, 5]. Hence Chi_7(r,2) = Chi_7(r,3)^2 = exp(2*Pi*I*(r-1)/3), Chi_7(r,4) = Chi_7(r,3)^4, Chi_7(r,5) = Chi_7(r,3)^5, Chi_7(r,6) = Chi_7(r,3)^3. Chi_7(r,1) = 1 and Chi_7(r,7) = 0, for r=1..6. This produces the character modulo 7 table. See the Apostol reference, p. 139, with interchanged rows r = 2..6. - _Wolfdieter Lang_, Jan 19 2017

T. M. Apostol, An Introduction to Analytic Number Theory, Springer-Verlag, NY, 1976, 1986, p. 139.
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).
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
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]

See A122028 (least primitive root that is prime), A001918 (least positive primitive root), A223942.

a[1] = 1; 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] = 1; a[n_] := SelectFirst[PrimitiveRootList[Prime[n]], PrimeQ]; Array[a, 101] (* Jean-François Alcover, Sep 28 2016 *)

leastroot(p)=forprime(q=2,p,if(znorder(Mod(q,p))+1==p,return(q)))
a(n)=if(n>1,leastroot(prime(n)),1) \\ Charles R Greathouse IV, Mar 20 2013

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

A229708 Least prime of maximal order mod n.

Original entry on oeis.org

2, 3, 2, 3, 2, 5, 3, 3, 2, 3, 2, 5, 2, 3, 2, 3, 3, 5, 2, 3, 2, 7, 5, 5, 2, 7, 2, 3, 2, 7, 3, 3, 2, 3, 2, 5, 2, 3, 2, 3, 7, 5, 3, 3, 2, 5, 5, 5, 3, 3, 5, 7, 2, 5, 2, 3, 2, 3, 2, 7, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 7, 5, 5, 5, 2, 3, 2, 7, 3, 3, 2, 7, 2, 5, 3, 3, 2

Offset: 1

Eric M. Schmidt, Sep 27 2013

a(prime(n)) = A122028(n).

Eric M. Schmidt, Table of n, a(n) for n = 1..10000

Cf. A111076, A122028.

def A229708(n) : m = Integers(n).unit_group_exponent(); return next(p for p in Primes() if n%p != 0 and mod(p,n).multiplicative_order() == m)

a(n) = A111076(n) if and only if A111076(n) is prime. - Jonathan Sondow, May 17 2017

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}]

A229709 Least sum of two squares that is a primitive root of the n-th prime.

Original entry on oeis.org

1, 2, 2, 5, 2, 2, 5, 2, 5, 2, 13, 2, 13, 5, 5, 2, 2, 2, 2, 13, 5, 29, 2, 13, 5, 2, 5, 2, 10, 5, 29, 2, 5, 2, 2, 13, 5, 2, 5, 2, 2, 2, 29, 5, 2, 34, 2, 5, 2, 10, 5, 13, 13, 18, 5, 5, 2, 26, 5, 13, 5, 2, 5, 17, 10, 2, 29, 10, 2, 2, 5, 13, 10, 2, 2, 5, 2, 5, 13

Offset: 1

Eric M. Schmidt, Sep 27 2013

nonn

			a(4) = 5 as 5 = 2^2 + 1^2 is a primitive root mod 7 (the 4th prime).

Eric M. Schmidt, Table of n, a(n) for n = 1..10000
Christopher Ambrose, On the Least Primitive Root Expressible as a Sum of Two Squares, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 13, Paper A55, 2013.

Cf. A001481, A122028, A229710.

def A229709(n) : p = nth_prime(n); return next(i for i in PositiveIntegers() if i%p!=0 and mod(i,p).multiplicative_order() == p-1 and all(q%4 != 3 or e%2==0 for (q,e) in factor(i)))

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

A002233 a(1) = 1; for n > 1, a(n) = least positive prime primitive root of n-th prime.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A229708 Least prime of maximal order mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Sage

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A229709 Least sum of two squares that is a primitive root of the n-th prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Sage

A263984 Least composite primitive root of n-th prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI