Sum of all possible remainders when $2^n$, where n is a nonnegative integer, is divided by 1000 
Let $R$ be the set of all possible remainders when a number of the
  form $2^n$, $n$ a nonnegative integer, is divided by $1000$. Let $S$
  be the sum of all elements in $R$. Find the remainder when $S$ is
  divided by $1000$.

I am trying to understand the provided solution:

Consider the subset $R'$ of $R$ consisting of only those numbers which
  are divisible by $8$, the highest power of $2$ dividing $1000$. Since
  $\gcd(2,125) = 1$, by the Chinese Remainder Theorem the elements of
  $R'$ cycle $\text{mod } 125$. Hence $R'$ stays the same $\text{mod }
> 1000$ when we multiply all elements by $2$. This means that if $S'$ is
  the sum of the elements of $R'$, then $S' \equiv 2S' \pmod{1000}$, so
  $S'$ is a multiple of $1000$. 
Since $S = 1 + 2 + 4 + S'$, $S$ is equivalent to $\boxed{7} \text{ mod
> } 1000$.

I do not understand how they applied the Chinese remainder theorem to arrive at the fact that the elements cycle mod $125$. Further, how does this allow them to conclude that $R'$ remains the same mod 1000 when all elements are multiplied by 2?
Finally, how did they get that $S = 1 + 2 + 4 + S'$?

Also, an alternate solution here relies on the fact that $2^0, 2^1,\ldots, 2^{99}$ are distinct modulo 125. They prove this as follows:

Suppose for the sake of contradiction that they are not. Then, we must
  have at least one of $2^{20}\equiv 1\pmod{125}$ or $2^{50}\equiv 1\pmod{125}$. However, writing $2^{10}\equiv 25 - 1\pmod{125}$, we can
  easily verify that $2^{20}\equiv -49\pmod{125}$ and $2^{50}\equiv -1\pmod{125}$, giving us the needed contradiction.

Here, how did they arrive at the fact that at least one will be true: $2^{20}\equiv 1\pmod{125}$ or $2^{50}\equiv 1\pmod{125}$?

Well for the second solution they used Euler's theorem
$$2^{\varphi(125)}\equiv2^{100}\equiv1\pmod{125}$$
So either $2^{50}\equiv-1\pmod{125}$ or $2^{20}\equiv 1\pmod{125}$
First part can be proved by euler's theorem since $2^{100k+n}\equiv2^{100k}\cdot2^{n}\equiv1\cdot2^{n}\pmod{125}$ it means it cycles $\pmod{125}$ note that maybe some divisor of $100$ raised to $2$ may also give residue $1$ divided by $\pmod{125}$
