cp's OEIS Frontend

A223934 Least prime p such that x^n-x-1 is irreducible modulo p.

%I A223934 #20 Feb 12 2019 04:04:39
%S A223934 2,2,2,3,2,2,7,2,17,7,5,3,3,2,109,3,101,19,229,5,2,23,23,17,107,269,2,
%T A223934 29,2,31,37,197,107,73,37,7,59,233,3,3,7,43,43,5,2,47,269,61,43,3,53,
%U A223934 13,3,643,13,5,151,59,2
%N A223934 Least prime p such that x^n-x-1 is irreducible modulo p.
%C A223934 Conjecture: a(n) < n*(n+3)/2 for all n>1.
%C A223934 Note that a(20) = 229 < 20*(20+3)/2 = 230.
%C A223934 The conjecture was motivated by E. S. Selmer's result that for any n>1 the polynomial x^n-x-1 is irreducible over the field of rational numbers.
%C A223934 We also conjecture that for every n=2,3,... there is a positive integer z not exceeding the (2n-2)-th prime such that z^n-z-1 is prime, and the Galois group of x^n-x-1 over the field of rationals is isomorphic to the symmetric group S_n.
%H A223934 Zhi-Wei Sun, <a href="/A223934/b223934.txt">Table of n, a(n) for n = 2..500</a>
%H A223934 E. S. Selmer, <a href="http://www.mscand.dk/article/view/10478/8499">On the irreducibility of certain trinomials</a>, Math. Scand., 4 (1956) 287-302.
%e A223934 a(8)=7 since f(x)=x^8-x-1 is irreducible modulo 7 but reducible modulo any of 2, 3, 5, for,
%e A223934    f(x)==(x^2+x+1)*(x^6+x^5+x^3+x^2+1) (mod 2),
%e A223934    f(x)==(x^3+x^2-x+1)*(x^5-x^4-x^3-x^2+x-1) (mod 3),
%e A223934    f(x)==(x^2-2x-2)*(x^6+2x^5+x^4+x^3-x^2-2) (mod 5).
%t A223934 Do[Do[If[IrreduciblePolynomialQ[x^n-x-1,Modulus->Prime[k]]==True,Print[n," ",Prime[k]];Goto[aa]],{k,1,PrimePi[n*(n+3)/2-1]}];
%t A223934 Print[n," ",counterexample];Label[aa];Continue,{n,2,100}]
%Y A223934 Cf. A000040, A220072, A217785, A217788, A218465.
%Y A223934 Cf. A002475 (n such that x^n-x-1 is irreducible over GF(2)).
%Y A223934 Cf. A223938 (n such that x^n-x-1 is irreducible over GF(3)).
%K A223934 nonn
%O A223934 2,1
%A A223934 _Zhi-Wei Sun_, Mar 29 2013