login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
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

%I #20 Apr 06 2013 18:38:44

%S 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,

%T 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

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

%C 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.

%C 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.

%C 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.

%C By the above "Reciprocity Law" in the case n=1, we have a(k) = A002233(k) for all k > 1.

%C Conjecture: a(n) <= sqrt(7*p_n) for all n>0.

%H Zhi-Wei Sun, <a href="/A223942/b223942.txt">Table of n, a(n) for n = 1..450</a>

%e a(9)=5 since f(x)=(x^{23}-1)/(x-1) is irreducible modulo 5, but reducible modulo either of 2 and 3, for,

%e f(x)==(x^{11}+x^9+x^7+x^6+x^5+x+1)

%e *(x^{11}+x^{10}+x^6+x^5+x^4+x^2+1) (mod 2)

%e and

%e f(x)==(x^{11}-x^8-x^6+x^4+x^3-x^2-x-1)

%e *(x^{11}+x^{10}+x^9-x^8-x^7+x^5+x^3-1) (mod 3).

%t 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]]]}];

%t Print[n," ",counterexample];Label[aa];Continue,{n,1,100}]

%Y Cf. A000040, A002233, A122028, A217785, A217788, A218465, A220072, A223934.

%K nonn

%O 1,1

%A _Zhi-Wei Sun_, Mar 29 2013

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 16:34 EDT 2024. Contains 371254 sequences. (Running on oeis4.)