Berkeley Math Circle

Solution:
Assume for contradiction this is not the case, and the polynomial can be written as
$$\left(x^{2}+x\right)^{2^{1000}}+1=f(x) g(x)$$
for some nonconstant $f$ and $g$ with integer coefficients. Clearly we may assume $f$ and $g$ have leading coefficient one. Taking modulo 2 we obtain that
$$f(x) g(x) \equiv\left(x^{2}+x\right)^{2^{1000}}+1 \equiv\left(x^{2}+x+1\right)^{2^{1000}} \quad(\bmod 2)$$
where the last step follows by noticing that $(a+b)^{2} \equiv a^{2}+b^{2}(\bmod 2)$.
As $x^{2}+x+1$ is irreducible modulo 2, it follows that we must have
$$f(x)=\left(x^{2}+x+1\right)^{\alpha}+2 \hat{f}(x)$$
and
$$g(x)=\left(x^{2}+x+1\right)^{\beta}+2 \hat{g}(x)$$
for some polynomials $\hat{f}, \hat{g}$ with integer coefficients, where $\alpha+\beta=1000$. By hypothesis, $\alpha, \beta \geq 1$.
Let $\varepsilon$ be a root to $x^{2}+x+1$, namely $\varepsilon=\frac{1}{2}(-1+i \sqrt{3})$. Substituting $\varepsilon$ into the original relation, we derive
$$2=(-1)^{2^{1000}}+1=4 \hat{f}(\varepsilon) \hat{g}(\varepsilon)$$
and hence $\frac{1}{2}=\hat{f}(\varepsilon) \hat{g}(\varepsilon)$. But we claim this is impossible. Indeed, the right-hand side is a polynomial in $\varepsilon$ with integer coefficients. Repeatedly applying the identity $\varepsilon^{2}=-(\varepsilon+1)$, we find that the right-hand side must be of the form $a+b \varepsilon$, where $a, b$ are integers. By equating real and imaginary parts this gives $a=\frac{1}{2}$ and $b=0$, which is a contradiction.