# how to find a relation between remainders when a sequence is given

I have a series that says $a_{n+1}=a_n^2+a_n$ and $a_1=3$ now I have to find $a_{1000} (\bmod{1000})$ now I calculated the remainder of numbers with respect to $1000$. thus $$a_1\equiv3(\bmod 1000)$$ $$a_2\equiv12(\bmod 1000)$$ $$a_3\equiv156(\bmod 1000)$$ $$a_4\equiv56^2+100\cdot56\cdot2+156(\bmod 1000)\equiv492(\bmod1000)$$ $$a_5\equiv92^2+2\cdot400\cdot92+492(\bmod 1000)\equiv556(\bmod1000)$$ $$a_6\equiv56^2+2\cdot500\cdot56+556(\bmod 1000)\equiv692(\bmod1000)$$ $$a_7\equiv92^2+2\cdot92\cdot600+692(\bmod 1000)\equiv556(\bmod1000)$$

now the sequence from $a_5$ to $a_{6}$ will keep on repeating thus we can calculate the remainder of $a_{1000}$ . now i am not particularly happy with my approach as this is brute force. is there any other approach to this question, which is more aesthetically pleasing, and is there a method to solve these type of questions in general.

## 1 Answer

Your approach is very probably the best available. However, your arithmetic is wrong: you can't drop the 100's digit when squaring each previous term.

If you do the arithmetic right, you find that $a_5 \equiv a_7 \equiv 556$ and $a_6 \equiv a_8 \equiv 692$ so the answer will be $692$.

• yes you are right , i thought $10^4$ term appears so i took it off , but i forgot that $10^2$ term also appears . – avz2611 Mar 18 '15 at 15:17