login
A223934
Least prime p such that x^n-x-1 is irreducible modulo p.
10
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,1
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.
LINKS
E. S. Selmer, On the irreducibility of certain trinomials, Math. Scand., 4 (1956) 287-302.
EXAMPLE
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).
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}]
CROSSREFS
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)).
Sequence in context: A048288 A050677 A058013 * A237531 A238504 A031356
KEYWORD
nonn
AUTHOR
Zhi-Wei Sun, Mar 29 2013
STATUS
approved