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?

  • $\begingroup$ 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 $\endgroup$ – Kirthi Raman Mar 10 '12 at 21:39
  • $\begingroup$ The numbers are too huge to focus on last digits only, I believe. $\endgroup$ – Lazar Ljubenović Mar 10 '12 at 21:50
  • $\begingroup$ What is the source of the problem? $\endgroup$ – Aryabhata Mar 10 '12 at 22:03
  • $\begingroup$ Serbian sub-regional competition 2004. $\endgroup$ – Lazar Ljubenović Mar 10 '12 at 22:06
  • $\begingroup$ All I know is if $p$ is prime then $(1+x)^{p} \equiv 1+x^{p}\hspace{4pt}({\text mod}\hspace{3pt} p)$ $\endgroup$ – Kirthi Raman Mar 10 '12 at 22:06

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.

| cite | improve this answer | |
  • 2
    $\begingroup$ Can you give some insight on how you found this. (Interesting approach) $\endgroup$ – Kirthi Raman Mar 10 '12 at 22:16
  • $\begingroup$ @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$ $\endgroup$ – Zero Mar 10 '12 at 22:21
  • $\begingroup$ @Kirthi You can find a couple algebraic derivations in my answer. $\endgroup$ – Gone Mar 10 '12 at 23:38
  • $\begingroup$ Thanks to both Bill Dubuque and Diego S. (I am catching up with what I have forgotten all these years) $\endgroup$ – 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$

Remark $ $ Generally $\,\rm x^2+x+1\mid x^I + x^J + x^K\ $ if $\rm \ \{I, J, K\}\equiv \{0,1,2\}\pmod 3,\,$ see here.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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