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.

  • $\begingroup$ 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. $\endgroup$ Apr 28, 2015 at 5:05

1 Answer 1


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$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .