elementary number theory - Prove that $n^{2003}+n+1$ is composite for every $nin mathbb{N} backslash{1}$

Prove that $n^{2003}+n+1$ is composite for every $n\in \mathbb{N} \backslash\{1\}$.

I tried with expanding $n^{2003}+1$, but I got nothing pretty not useful. I also couldn't get any improvement, let alone contradiction for assuming $n^{2003}+n+1=pq$ where $p,q\not= 1$. How should I do this and are there general tips on how to approach these problems, what to think about?

Answer

Let $w=e^{i2\pi/3}$. It's easy to see that $w$ and $w^2$ are all the roots of $x^2+x+1$ and roots of $x^{2003}+x+1$, therefore $x^2+x+1|x^{2003}+x+1$. So we have That $x^{2003}+x+1=(x^2+x+1)P(x)$, where $P(x)$ is some polynomial with integer coefficients. For $x\ge 2$, $x^{2003}+x+1$ is much bigger than $x^2+x+1$ so $P(x)$ is some integer greater than $2$ from which the conclusion follows.