For which $n \in \mathbb{N}$ $f(x) = x^{2n}+x^n+1$ is irreducible in $\mathbb{F}_2[x]$?

Question

I have $$f(x) = x^{2n}+x^n+1 \in \mathbb{F}_2[x].$$ When is this polynomial irreducible? It is obvious that for even $n$ this polynomial is reducible. But I don't have any idea about odd $n$.

Answer 1

Before we delve into $\Bbb{F}_2[x]$ let's consider the irreducibility of $f(x)$ in $\Bbb{Z}[x]$. Because $$ f(x)(x^n-1)=x^{3n}-1, $$ the zeros of $f$ are roots of unity of order dividing $3n$.This makes us consider the cyclotomic polynomial $\Phi_{3n}(x)\in \Bbb{Z}[x]$. Its degree is given by the Euler (totient) function $\phi(3n)$. If $n$ is divisible by an odd prime $p$ other than $3$, then $$ \phi(3n)\le \frac{3-1}3\cdot\frac{p-1}p\cdot3n<2n. $$ This means that for $f(x)$ to be irreducible in $\Bbb{Z}[x]$ it is necessary that $n$ is a power of three. The usual business with cyclotomic polynomials shows that this condition is also sufficient for irreducibility in $\Bbb{Z}[x]$.

A less trivial fact is that when $n=3^k$ the polynomial $f(x)$ remains irreducible in $\Bbb{F}_2[x]$ as well. This is a consequence of the fact that $2$ is a primitive root modulo $3^{k+1}$. I don't want to repeat the argument here. Instead, I refer you to an earlier answer of mine. See the addendum for the gory details.