Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

2 Answers

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|improve this answer
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. –  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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.