http://www.artofproblemsolving.com/Forum/viewtopic.php?f=38&t=49799 is of interest.

POTD 2006 in efnet #math. http://www.efnet-math.org/w/POTD_2006-12 I typed an alternative solution using just a bit of galois theory. http://www.efnet-math.org/math_tech/BonusProbDec0806.pdf

This is slightly different than the one given in the thread, but I think it works? Note that $(X^2+X)^{2^n}+1=(X^2+X+1)^{2^n}$ in $\mathbb{F}_2$. Suppose $(X^2+X)^{2^n}+1=fg$ where $f,g$ are integer, non-constant polynomials. Then it follows $\overline{fg}=(X^2+X+1)^{2^n}$. Since $X^2+X+1$ is irreducible in $\mathbb{F}_2$, it follows $\overline{f}=(X^2+X+1)^a$ and $\overline{g}=(X^2+X+1)^b$ where $a+b=2^n$. Going back to the problem, it follows for some $f_1, g_1$, we have $f=2f_1+(X^2+X+1)^a$ and $g=2g_1+(X^2+X+1)^b$. Substituting $f_1, g_1$, we get that $(X^2+X)^{2^n}+1=fg = (X^2+X+1)^{2^n}+4f_1g_1+2g_1(X^2+X+1)^b+2f_1(X^2+X+1)^a$. Note the only binomial coefficients of form $\binom{2^n}{i}$ which are not multiples of 4 are when $i=0, 2^{n-1}, 2^n$. Thus, taking mod 4, we get $(X^2+X)^{2^n}+1\equiv (X^2+X)^{2^n}+2(X^2+X)^{2^{n-1}}+1+2g_1(X^2+X+1)^b+2f_1(X^2+X+1)^a$. Canceling terms and dividing by 2, we get $(X^2+X)^{2^{n-1}}=g_1(X^2+X+1)^b+f_1(X^2+X+1)^a$ in $\mathbb{F}_2$. On the other hand, if $ab>0$, this means $X^2+X+1\mid (X^2+X)^{2^{n-1}}$, which is a clear contradiction. Thus, one of $a,b=0$. WLOG, $a=0$. Then $b=2^n$. This means that $(2f_1+1)(2g_1+(X^2+X+1)^{2^n})=(X^2+X)^{2^n}+1$. On the other hand, note that the degree of $2g_1+(X^2+X+1)^{2^n}$ is at least $2^{n+1}$. Thus, it follows the degree of $f=2f_1+1$ is at most $0$, so $f$ is constant, contradiction again. Thus, the problem is solved.

I think this might be faster...

@above, Your lemma is trivial by Lucas' Theorem because all such $k$ have a positive digit where $p^n$ has a zero in its base $p$ representation, and since $\binom{0}{m}=0$ for positive integers $m$, we are done.

Assume ftsoc there exist two integers polynomials $p, q$ with positive degree such that $p(x)q(x) = f(x)$. In $\mathbb{F}_2$ we have $\overline{p(x)}\cdot \overline{q(x)} = \overline{p(x)q(x)} = \overline{f(x)} = (x^2 + x + 1)^{2^n}$, so for some positive integers $p_1 + q_1 = 2^n$ (if either of $p_1, q_1$ is $0$ then the other equals $2^n$, so one of $p$ and $q$ has degree $2^n$ and the other is constant) we have $\overline{p(x)} = (x^2 + x + 1)^{p_1}$ and $\overline{q(x)} = (x^2 + x + 1)^{q_1}$. Thus, for some integral polynomials $p_2, q_2$, we can write $p(x) = (x^2 + x + 1)^{p_1} + 2p_2(x)$ and $q(x) = (x^2 + x + 1)^{q_1} + 2q_2(x)$. Then, taking $\omega \in \{e^{2 \pi i/3}, e^{4 \pi i/3}\}$ which satisfies $\omega^2 + \omega + 1 = 0$, we see that $$2 = (\omega^2 + \omega)^{2^n} + 1 = f(\omega) = p(\omega)q(\omega) = 4p_2(\omega)q_2(\omega).$$By repeatedly using the fact that $\omega^2 = -\omega - 1$, we find there exist integers $a, b$ such that $p_2(\omega)q_2(\omega) = a\omega + b$. So, $a\omega + b = \tfrac{1}{2}$, which implies that $a = 0$ and $b = \tfrac{1}{2}$, contradicting the fact that $b$ is an integer. Therefore $f$ is indeed irreducible.