login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A223942 Least prime q such that (x^{p_n}-1)/(x-1) is irreducible modulo q, where p_n is the n-th 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^{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.

LINKS

Zhi-Wei Sun, Table of n, a(n) for n = 1..450

EXAMPLE

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

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

Zhi-Wei Sun, Mar 29 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 7 00:44 EST 2019. Contains 329816 sequences. (Running on oeis4.)