# Finding the remainder

Corresponding terms from the sequence $1,2,3,4,5...$ and $2^1,2^2,2^3,2^4,2^5,...$, are multiplied, creating the sequence $1\times 2^1,2\times 2^2,3\times 2^3,4\times 2^4,5\times 2^5...$. Let $A$ be the sum of the first $2011$ numbers in the new sequence. Find the remainder when $A$ is divided by $1000$

My solution:

$2S-S=2010 \cdot 2^{2012}+2$. Then $2^{2012} \equiv 2^{12} \mod{125} \equiv 96 \mod{125}$ $2010 \cdot 2^{2012} \equiv 10 \cdot 96 \mod{1000} \equiv 960 \mod{1000}$ Add 2 and the answer is $962$

-
Yes that's right. – anon Jul 21 '12 at 3:13

The solution is correct. The step $2^{2012}\equiv2^{12}\bmod125$ uses Euler's theorem together with $\phi(5^3)=5^3-5^2=100$. The remainder $2^{2012}\equiv96\bmod1000$ is being computed by computing the remainders modulo the prime powers $5^3=125$ and $2^3=8$ and noting that the remainder $\bmod8$ is $0$. Alternatively, you could have used $\phi(5^3\cdot2^3)=(5^3-5^2)(2^3-2^2)=400$ directly to get $2^{2012}\equiv2^{12}\equiv96\bmod1000$.