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}$?


1 Answer 1


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}$

  • $\begingroup$ Wait... how did you jump from $$2^{100}\equiv1\pmod{125}$$ to $2^{50}$ and $2^{20}$? Why did you choose $50$ and $20$ as the exponents? And why must one of them be congruent to 1 mod 125? $\endgroup$
    – 1110101001
    Aug 12, 2014 at 20:21
  • 1
    $\begingroup$ @user2612743 If we say that they are distinct than only one of them must give residue one,otherwise they cycle.Now only divisors of $100$ may give residue $1$ when divided by $125$ otherwise the property $2^{100k+n}\equiv2^n\pmod{125}$ would fail.Now clearly if neither $2^{20}$ or $2^{50}$ give the residue $1$ than neither do $2^1,2^2,2^4,2^5,2^10,2^25$ since if for example $2^4$ gives residue $1$ than also $(2^4)^5\equiv1^5\equiv1\pmod{125}$ $\endgroup$
    – kingW3
    Aug 12, 2014 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.