|
%I #20 Feb 12 2019 04:04:39
%S 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 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 13,3,643,13,5,151,59,2
%N Least prime p such that x^n-x-1 is irreducible modulo p.
%C Conjecture: a(n) < n*(n+3)/2 for all n>1.
%C Note that a(20) = 229 < 20*(20+3)/2 = 230.
%C 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 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 Zhi-Wei Sun, <a href="/A223934/b223934.txt">Table of n, a(n) for n = 2..500</a>
%H 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 a(8)=7 since f(x)=x^8-x-1 is irreducible modulo 7 but reducible modulo any of 2, 3, 5, for,
%e f(x)==(x^2+x+1)*(x^6+x^5+x^3+x^2+1) (mod 2),
%e f(x)==(x^3+x^2-x+1)*(x^5-x^4-x^3-x^2+x-1) (mod 3),
%e f(x)==(x^2-2x-2)*(x^6+2x^5+x^4+x^3-x^2-2) (mod 5).
%t 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 Print[n," ",counterexample];Label[aa];Continue,{n,2,100}]
%Y Cf. A000040, A220072, A217785, A217788, A218465.
%Y Cf. A002475 (n such that x^n-x-1 is irreducible over GF(2)).
%Y Cf. A223938 (n such that x^n-x-1 is irreducible over GF(3)).
%K nonn
%O 2,1
%A _Zhi-Wei Sun_, Mar 29 2013
|
