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

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, 29, 2, 31, 37, 197, 107, 73, 37, 7, 59, 233, 3, 3, 7, 43, 43, 5, 2, 47, 269, 61, 43, 3, 53, 13, 3, 643, 13, 5, 151, 59, 2

Offset: 2

Author

Zhi-Wei Sun, Mar 29 2013

Keywords

• nonn

Comments

Conjecture: a(n) < n*(n+3)/2 for all n>1.

Note that a(20) = 229 < 20*(20+3)/2 = 230.

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.

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.

Examples

			a(8)=7 since f(x)=x^8-x-1 is irreducible modulo 7 but reducible modulo any of 2, 3, 5, for,
   f(x)==(x^2+x+1)*(x^6+x^5+x^3+x^2+1) (mod 2),
   f(x)==(x^3+x^2-x+1)*(x^5-x^4-x^3-x^2+x-1) (mod 3),
   f(x)==(x^2-2x-2)*(x^6+2x^5+x^4+x^3-x^2-2) (mod 5).
		

Links

• Zhi-Wei Sun, Table of n, a(n) for n = 2..500
• E. S. Selmer, On the irreducibility of certain trinomials, Math. Scand., 4 (1956) 287-302.

Crossrefs

Cf. A000040, A220072, A217785, A217788, A218465.

Cf. A002475 (n such that x^n-x-1 is irreducible over GF(2)).

Cf. A223938 (n such that x^n-x-1 is irreducible over GF(3)).

Programs

Mathematica

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]}];
Print[n," ",counterexample];Label[aa];Continue,{n,2,100}]