A107751

[Edwin Clark]

On Fri, 12 Oct 2007, Robert Israel wrote:

> You may have noticed that (at least for n up to 200) whenever your polynomial 
> x^n+x+1 factors, one of the factors is x^2+x+1.  I don't
> know if this is true for all n, but if so there's doubtless a good
> reason for it.  In any case it's easy to see that for n >= 2, x^n+x+1
> is divisible by x^2+x+1 if and only if n == 2 mod 3.
>

According to

     http://www.math.niu.edu/~rusin/known-math/95/trinom:

The polynomial x^k+x+1 has the factor x^2+x+1 if k is 2 (mod 3) and is 
otherwise irreducible.

The reference given there by David Eppstein is:

Ernst Selmer, "On the irreducibility of certain trinomials", Math. 
Scand. 4 (1956) 287-302