cp's OEIS Frontend

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

%I A376950 #18 Nov 03 2024 09:32:00
%S A376950 3,31,193,211,4339,41143,20347,8196919,152305817,1741273,8262307441,
%T A376950 853465946651,52120172761
%N A376950 Smallest prime p such that x^n + x + 1 splits modulo p.
%C A376950 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 A376950 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 A376950 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 A376950 a(n) is the smallest prime p such that x^n + x + 1 has n (not necessarily distinct) roots modulo p.
%C A376950 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 A376950 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 A376950 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 A376950 f:= proc(n) local P,F,p,x;
%p A376950   P:= x^n+x+1;
%p A376950   p:= 1;
%p A376950   do
%p A376950     p:= nextprime(p);
%p A376950     F:= map(degree,(Factors(P) mod p)[2][..,1],x);
%p A376950     if max(F) = 1 then return p fi
%p A376950   od
%p A376950 end proc:
%p A376950 map(f, [$2..8]); # _Robert Israel_, Oct 10 2024
%t A376950 a[n_] := Module[{i},
%t A376950  For[i = 1, True, i++,
%t A376950   If[Total[Last /@ Rest[FactorList[x^n + x + 1, Modulus -> Prime[i]]]] == n,
%t A376950    Return[Prime[i]];
%t A376950   ]
%t A376950  ]
%t A376950 ];
%t A376950 a /@ Range[2, 8]
%Y A376950 Cf. A377496.
%K A376950 nonn,hard,more
%O A376950 2,1
%A A376950 _Ben Whitmore_, Oct 10 2024