Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
The fact that $2003$ is a prime makes this question harder. I tried for $n=2$ and the last two digits are $11$. Not sure if you could just focus on last few digits and show they are composite – Kirthi Raman Mar 10 '12 at 21:39
The numbers are too huge to focus on last digits only, I believe. – Lazar Ljubenović Mar 10 '12 at 21:50
What is the source of the problem? – Aryabhata Mar 10 '12 at 22:03
Serbian sub-regional competition 2004. – Lazar Ljubenović Mar 10 '12 at 22:06
All I know is if $p$ is prime then $(1+x)^{p} \equiv 1+x^{p}\hspace{4pt}({\text mod}\hspace{3pt} p)$ – Kirthi Raman Mar 10 '12 at 22:06
up vote 17 down vote accepted

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.

share|cite|improve this answer
Can you give some insight on how you found this. (Interesting approach) – Kirthi Raman Mar 10 '12 at 22:16
@KirthiRaman I noticed that $2003\equiv 2\pmod{3}$ and that the polynomial $n^{2003}+n+1$ have only 1's and 0's as coefficients. This approach can be generalized to polynomials of the form $x^m+x^{m-1}+...+x+1$, for example $1+x+x^2+x^3|x^{23}+x^6+x+1$ – Zero Mar 10 '12 at 22:21
@Kirthi You can find a couple algebraic derivations in my answer. – Bill Dubuque Mar 10 '12 at 23:38
Thanks to both Bill Dubuque and Diego S. (I am catching up with what I have forgotten all these years) – Kirthi Raman Mar 11 '12 at 1:05

Hint $\rm\ f = x^{3n+2}+x+1\ = \ x^2\:(x^{3n}-1) + x^2+x+1\ $

therefore $\rm\:x^2+x+1\ |\ x^3-1\ |\ x^{3n}-1\:\Rightarrow\: x^2+x+1\ |\ f$

Or, $\rm\ mod\ x^2+x+1\!:\ x^3\equiv 1\ \Rightarrow\ x^{3n+2}+x+1\equiv (x^3)^n x^2 + x + 1 \equiv x^2+x+1\equiv 0$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.