

A223942


Least prime q such that (x^{p_n}1)/(x1) is irreducible modulo q, where p_n is the nth prime.


2



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

It is well known that (x^{p^n}1)/(x^{p^{n1}}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^{n1}}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^{n1}}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^np^{n1}. Note that gcd(x^{p^n}1,x^{q^k1}1) = x^{gcd(p^n,q^k1)}1. If p^n  q^k1, 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^k1, then gcd(x^{p^n}1,x^{q^k1}1) divides x^{p^{n1}}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^k1 for no 0 < k < p^np^{n1}, 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.


LINKS

ZhiWei Sun, Table of n, a(n) for n = 1..450


EXAMPLE

a(9)=5 since f(x)=(x^{23}1)/(x1) 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^8x^6+x^4+x^3x^2x1)
*(x^{11}+x^{10}+x^9x^8x^7+x^5+x^31) (mod 3).


MATHEMATICA

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


CROSSREFS

Cf. A000040, A002233, A122028, A217785, A217788, A218465, A220072, A223934.
Sequence in context: A257572 A160493 A053760 * A278597 A138789 A129654
Adjacent sequences: A223939 A223940 A223941 * A223943 A223944 A223945


KEYWORD

nonn


AUTHOR

ZhiWei Sun, Mar 29 2013


STATUS

approved



