A376950 - OEIS

%I #18 Nov 03 2024 09:32:00

%S 3,31,193,211,4339,41143,20347,8196919,152305817,1741273,8262307441,

%T 853465946651,52120172761

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

%C 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|.

%C 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).

%C 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).

%C a(n) is the smallest prime p such that x^n + x + 1 has n (not necessarily distinct) roots modulo p.

%C 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.

%H Ernst S. Selmer, <a href="https://doi.org/10.7146/math.scand.a-10478">On the irreducibility of certain trinomials</a>, Mathematica Scandinavica 4 (1956), 287-302.

%e 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.

%p f:= proc(n) local P,F,p,x;

%p   P:= x^n+x+1;

%p   p:= 1;

%p   do

%p     p:= nextprime(p);

%p     F:= map(degree,(Factors(P) mod p)[2][..,1],x);

%p     if max(F) = 1 then return p fi

%p   od

%p end proc:

%p map(f, [$2..8]); # _Robert Israel_, Oct 10 2024

%t a[n_] := Module[{i},

%t  For[i = 1, True, i++,

%t   If[Total[Last /@ Rest[FactorList[x^n + x + 1, Modulus -> Prime[i]]]] == n,

%t    Return[Prime[i]];

%t   ]

%t  ]

%t ];

%t a /@ Range[2, 8]

%Y Cf. A377496.

%K nonn,hard,more,new

%O 2,1

%A _Ben Whitmore_, Oct 10 2024