1
$\begingroup$

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

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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

$\endgroup$
2
  • $\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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .