We have that $x_{n+1}=x_n+x_n^2$ hence all $x_n$ are even. We will prove by a backward induction that $x_2$ must be divisible by $1003$. $x_{n}\equiv 0 (\mod 1003)\Leftrightarrow x_{n-1}^2+x_{n-1}\equiv 0 (\mod 1003)\Leftrightarrow x_{n-1}\equiv -1$ or $x_{n-1}\equiv 0 (\mod 1003)$. We will prove that $x_{n-1}\equiv -1$ cannot hold for $n-1\ge 2$: $x_{n-1}=x_{n-2}^2+x_{n-2}\equiv -1 (\mod 1003)\Leftrightarrow (2x_{n-2}+1)^2\equiv -3 (\mod 1003)$. But from quadratic reciprocity law we get that $3$ is quadratic residue $\mod 1003$, but since $1003=4\cdot 250+3$ we have that $-1$ is not a quadratic residue $(\mod 1003)$. Hence contradiction. Since $1003\mid x_2$, we have that $x_1\equiv 0,-1 (\mod 1003)$. Hence the least value for $x_1$ is 1002, which works.

I think $x_1=1.$ But i am wrong. Let y=x(x+1)(mod 1003). If y=0, then x=0 or x=-1 (mod 1003). If y=-1=x(x+1) we have $(2x+1)^2=3 (mod 1003)$. It give contradition, because $(\frac{3}{1003})=-(\frac{1003}{3})=-1$. Therefore if $x_1\not= 0,-1$, then $1003\not | x_n$ for all n>1.

I proved that it is not 1.

You prove: if $x_1=0,-1(mod 1003)$, then $2006|x_n$ for n>1. But you don't prove, that $x_1\not =0,-1$ don't work.

I agree that $x_{n+1}=x_n^2+x_n$ but only for $n\geq 2$ . Since from the question we can see that $x_2=x_1^2\not =x_1+x_1^2$ @Rust : The question does say " Positive Integer " , so I think we doesnt have to prove the case for $x_1=0,-1$ .

There is some part not complete since I cant prove it , but i think it is true . I claim that $x_1=472$ From question , $x_2=x_1^2$ and $x_n=x_{n-1}(1+x_{n-1})$ for $n\geq 3$ Or $x_n=x_1^2(x_2+1)(x_3+1)\cdots (x_{n-1}+1)$ ,$n\geq 3$ .....(i) Since any $(x_i+1,x_j+1)=1$ and $(x_i+1,x_1)=1$ , the terms are all pairwise coprime . We also notice that $x_n$ is even for all $n\geq 3$ and $x_1^2(x_2+1)$ is even . If $x_{2006}$ is divisible by $2006=2\cdot 17\cdot 59$ , then we know that there must be ONLY one $x_i+1$ or $x_1$ who has the factor of $17$ or $59$ . If it is $x_k+1$ ($k\geq 3)$ who has the factor of $17$ or $59$ , then (i) $x_k+1\equiv 0\mod 59$ $\implies x_{k-1}(x_{k-1}+1)\equiv -1\mod 59$ Here is the part I dont know how to prove but i think there is no solution for $x_{k-1}$ which satisfy this ? if that is true , then we can say that it is either $x_2+1$ or $x_1$ who has the factor of $59$ . But $x_2+1\equiv 0\mod 59$ $\implies x_1^2\equiv -1\mod 59$ (anyway to prove no solution for this other that brute force all cases?) . Hence we conclude $x_1\equiv 0\mod 59$......(i) (ii)As for the factor of $17$ , we do the same way and found that it must also be either $x_2+1$ or $x_1$ who has the factor of $17$ . But $x_2+1\equiv 0\mod 17$ $\implies x_1\equiv \pm 4\mod 17$ .....(ii) (another case is $x_1\equiv 0\mod 17$ but that will give us $x_1\equiv 0\mod 1003$ when combine with (ii) ) Hence by (i),(ii) , we use Chinese Remainder Theorem and conclude that either $x_1\equiv 472\mod 1003$ or $\equiv 531\mod 1003$ . So the smallest such $x_1$ is $\boxed{472}$ Someone plz complete the "incomplete" part for me to make this solution valid

shyong wrote: $\implies x_{k-1}(x_{k-1}+1)\equiv -1\mod 59$ Here is the part I dont know how to prove but i think there is no solution for $x_{k-1}$ which satisfy this ? Someone plz complete the "incomplete" part for me to make this solution valid You need to show that the equation $x^2 +x +1\equiv 0 (\mod 59 )$ does not has solution in $Z_{59}$ This is equivalent to $(2x +1)^2 = -3 (\mod 59)$ Now $(\frac{56}{59})= (\frac{7}{59}) (\frac{2}{59})^3= (\frac{59}{7})=(\frac 37)=-1$ , because $(\frac{2}{prime(8k+3)} )=-1.$ Hence -3 is not quadratic residue modulo 59 !

which solution is true?

xirti wrote: We have that $x_{n+1}=x_n+x_n^2$ hence all $x_n$ are even. We will prove by a backward induction that $x_2$ must be divisible by $1003$. $x_{n}\equiv 0 (\mod 1003)\Leftrightarrow x_{n-1}^2+x_{n-1}\equiv 0 (\mod 1003)\Leftrightarrow x_{n-1}\equiv -1$ or $x_{n-1}\equiv 0 (\mod 1003)$. We will prove that $x_{n-1}\equiv -1$ cannot hold for $n-1\ge 2$: $x_{n-1}=x_{n-2}^2+x_{n-2}\equiv -1 (\mod 1003)\Leftrightarrow (2x_{n-2}+1)^2\equiv -3 (\mod 1003)$. But from quadratic reciprocity law we get that $3$ is quadratic residue $\mod 1003$, but since $1003=4\cdot 250+3$ we have that $-1$ is not a quadratic residue $(\mod 1003)$. Hence contradiction. Since $1003\mid x_2$, we have that $x_1\equiv 0,-1 (\mod 1003)$. Hence the least value for $x_1$ is 1002, which works. Hy I can't get something 1003 is not a prime number so how can you apply Gauss lemma in your first line ?

shyong wrote: There is some part not complete since I cant prove it , but i think it is true . I claim that $x_1=472$ From question , $x_2=x_1^2$ and $x_n=x_{n-1}(1+x_{n-1})$ for $n\geq 3$ Or $x_n=x_1^2(x_2+1)(x_3+1)\cdots (x_{n-1}+1)$ ,$n\geq 3$ .....(i) Since any $(x_i+1,x_j+1)=1$ and $(x_i+1,x_1)=1$ , the terms are all pairwise coprime . We also notice that $x_n$ is even for all $n\geq 3$ and $x_1^2(x_2+1)$ is even . If $x_{2006}$ is divisible by $2006=2\cdot 17\cdot 59$ , then we know that there must be ONLY one $x_i+1$ or $x_1$ who has the factor of $17$ or $59$ . If it is $x_k+1$ ($k\geq 3)$ who has the factor of $17$ or $59$ , then (i) $x_k+1\equiv 0\mod 59$ $\implies x_{k-1}(x_{k-1}+1)\equiv -1\mod 59$ Here is the part I dont know how to prove but i think there is no solution for $x_{k-1}$ which satisfy this ? if that is true , then we can say that it is either $x_2+1$ or $x_1$ who has the factor of $59$ . But $x_2+1\equiv 0\mod 59$ $\implies x_1^2\equiv -1\mod 59$ (anyway to prove no solution for this other that brute force all cases?) . Hence we conclude $x_1\equiv 0\mod 59$......(i) (ii)As for the factor of $17$ , we do the same way and found that it must also be either $x_2+1$ or $x_1$ who has the factor of $17$ . But $x_2+1\equiv 0\mod 17$ $\implies x_1\equiv \pm 4\mod 17$ .....(ii) (another case is $x_1\equiv 0\mod 17$ but that will give us $x_1\equiv 0\mod 1003$ when combine with (ii) ) Hence by (i),(ii) , we use Chinese Remainder Theorem and conclude that either $x_1\equiv 472\mod 1003$ or $\equiv 531\mod 1003$ . So the smallest such $x_1$ is $\boxed{472}$ Someone plz complete the "incomplete" part for me to make this solution valid You're right, that is the right value. My solution is similar to xirti one, but the problem in his solution is that he forget some Ideas, this is a correct form.

I find that x_1=118 satisfies the problem, (since x-2=118*119=7*2006) thus all x_i greater than 1 is divisible by 2006. for this reason consider the first index d such that 17 or 59 ( no matter because they have reminder -1 while dividing by 6)divide x_d . thus we must have x_d =-1 (mod 17 or 59) and (x_d-1)^2 +x_d-1+1=0 (mod 17 or 59) but all of primes dividing x^2 +x+1 is of the form 6k+1. contradiction. thus we must have this cases: x_1 =-1(mod 59,17) x_1=0 (mod 17) and -1 (mod 59) and x_1=-1(mod 17) and x_1=0 (mod 59). after some calculations we can see that 118 obtained from the third cases.

I think you made a mistake $ x_{2}=x_{1}^{2} $