# Irreducibility of $x^{2n}+x^n+1$

I want to know for what $n$, $$x^{2n}+x^n+1$$ is irreducible modulo 2. I think for $n=3^k$ but have no idea how to prove it.

• When $n=3^k$ I happened to use this family of polynomials as an example here. Jack's excellent answer gives you everything you need. Buried in my answer is a proof by induction of the necessary parts of Jack's equation (3) in case that's giving you a headache. A cleaner way of seeing that probably exists. Apr 28, 2015 at 5:05

If $\omega=\exp\left(\frac{2\pi i}{3}\right)$, the cyclotomic polynomial $\Phi_3(x)$ equals: $$\Phi_3(x)=\frac{x^3-1}{x-1}=x^2+x+1=(x-\omega)(x-\bar{\omega})\tag{1}$$ and since: $$\omega^{2n}+\omega^n+1 = 3\cdot\mathbb{1}_{n\equiv 0\pmod{3}}(n) \tag{2}$$ we have that $\Phi_3(x)$ is a divisor of $x^{2n}+x^n+1$ for every $n$ that is not a multiple of three.
For the same reason, if $n$ is not a power of three and $m=\nu_3(n)$, we have that $\Phi_3(x^{3^m})$ is a divisor of $x^{2n}+x^n+1$, so $n=3^k$ is a necessary condition for $x^{2n}+x^n+1=\Phi_3(x^n)$ to be irreducible over $\mathbb{F}_2$. It is also a sufficient condition: we just need to recall that $$\nu_3\left(4^h-1\right) = 1+\nu_3(h).\tag{3}$$ I leave it to you to understand why the last line implies the irreducibility of $\Phi_3(x^{3^k})$ over $\mathbb{F}_2$.