OFFSET
2,1
COMMENTS
Let f be a polynomial with rational coefficients and G be its Galois group. By the Chebotarev density theorem, f splits modulo infinitely many primes, and the density of such primes is 1/|G|.
If n == 0 or 1 (mod 3) or n = 2 then x^n + x + 1 is irreducible over the rationals, and if n == 2 (mod 3) and n > 2 then it factors into the product of a quadratic and an irreducible factor of degree n-2 (see reference to Selmer, Theorem 1).
For all n, it appears that the Galois group of x^n + x + 1 is as large as possible, i.e. of order n! for n == 0 or 1 (mod 3), and of order 2*(n-2)! for n == 2 (mod 3).
a(n) is the smallest prime p such that x^n + x + 1 has n (not necessarily distinct) roots modulo p.
For n > 3, it appears that all roots of x^n + x + 1 are distinct modulo a(n). For n = 2 and n = 3, there is a repeated root modulo a(n). The smallest primes modulo which x^2 + x + 1 and x^3 + x + 1 split with no repeated roots are 7 and 47 respectively.
LINKS
Ernst S. Selmer, On the irreducibility of certain trinomials, Mathematica Scandinavica 4 (1956), 287-302.
EXAMPLE
a(4) = 193 because x^4 + x + 1 has an irreducible factor of degree > 1 modulo all primes less than 193, but splits as (x + 135)(x + 145)(x + 148)(x + 151) modulo 193.
MAPLE
f:= proc(n) local P, F, p, x;
P:= x^n+x+1;
p:= 1;
do
p:= nextprime(p);
F:= map(degree, (Factors(P) mod p)[2][.., 1], x);
if max(F) = 1 then return p fi
od
end proc:
map(f, [$2..8]); # Robert Israel, Oct 10 2024
MATHEMATICA
a[n_] := Module[{i},
For[i = 1, True, i++,
If[Total[Last /@ Rest[FactorList[x^n + x + 1, Modulus -> Prime[i]]]] == n,
Return[Prime[i]];
]
]
];
a /@ Range[2, 8]
CROSSREFS
KEYWORD
nonn,hard,more,new
AUTHOR
Ben Whitmore, Oct 10 2024
STATUS
approved