$X^n + X + 1$ reducible in $\mathbb{F}_2$ I was told that sometimes in characteristic 2 that $X^n + X + 1$ is reducible mod 2. What is the smallest $n$ where that is true?

Well, that was easy: $n=5$ is the smallest value of $n$ for which $x^n+x+1$ is reducible. Indeed, $x^5+x+1=(x^2+x+1)(x^3+x^2+1)$. The other values for wich $x^n+x+1$ is reducible in $\mathbf F_2[x]$ are, for $n<100$:
8,
10,
11,
12,
13,
14,
16,
17,
18,
19,
20,
21,
23,
24,
25,
26,
27,
29,
31,
32,
33,
34,
35,
36,
37,
38,
39,
40,
41,
42,
43,
44,
45,
47,
48,
49,
50,
51,
52,
53,
54,
55,
56,
57,
58,
59,
61,
62,
64,
65,
66,
67,
68,
69,
70,
71,
72,
73,
74,
75,
76,
77,
78,
79,
80,
81,
82,
83,
84,
85,
86,
87,
88,
89,
90,
91,
92,
93,
94,
95,
96,
97,
98,
99
I determined this with a little sage program:
A.<x>=PolynomialRing(GF(2))
for i in range(2,100):
    if not((x^i+x+1).is_irreducible()):
        print i

