# Prove that $n^{2003}+n+1$ is composite for every $n\in \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?

-

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
show 1 more comment

## 2 Answers

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.

-

2
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$ – xD13G0x Mar 10 '12 at 22:21
@Kirthi You can find a couple algebraic derivations in my answer. – Gone 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$

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 32, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9397120475769043, "perplexity_flag": "middle"}