A376950 Smallest prime p such that x^n + x + 1 splits modulo p.

3, 31, 193, 211, 4339, 41143, 20347, 8196919, 152305817, 1741273, 8262307441, 853465946651, 52120172761

Offset: 2

Author

Ben Whitmore, Oct 10 2024

Keywords

• nonn
• hard
• more

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.

Examples

			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.
		

Links

• Ernst S. Selmer, On the irreducibility of certain trinomials, Mathematica Scandinavica 4 (1956), 287-302.

Crossrefs

Cf. A377496.

Programs

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]