2
$\begingroup$

Hints Only

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

Hints Only

$2^1 \equiv 2, 2^2 \equiv 4, 2^3 \equiv 8, 2^4 \equiv 16, 2^5 \equiv 32, 2^6 \equiv 64, 2^7 \equiv 128, 2^8 \equiv 256, 2^9 \equiv 512$.

I tried many values of $2^x$ to notice a pattern.

$2^{10} \equiv 24 \pmod{1000}$ and $2^{11} = 48 \pmod{1000}$ and this pattern continue until some point, but then stops.

I am not sure if $2^k \pmod{1000}$ ever cycles back.

But since computing $2^k \pmod{1000}$ is pretty quick I went ahead and found:

$2^{12} \equiv 96, 2^{13} \equiv 192, 2^{14} \equiv 184, 2^{15} \equiv 368, 2^{16} \equiv 736, 2^{17} \equiv 472, 2^{18} \equiv 944, 2^{19} \equiv 888, 2^{20} \equiv 776, 2^{21} \equiv 552, 2^{22} \equiv 104, 2^{23} \equiv 208, 2^{24} \equiv 416, 2^{25} \equiv 832, 2^{26} \equiv 664$.

And I see absolutely no recurring pattern. But I do realize it has to stop somewhere since it cant be an infinite sum.

like:

$$2^{4k + n} \equiv 2^{n} \pmod{10}$$

Hints Only

  • EDIT

using $a^{\phi(x)} \equiv 1 \pmod{x}$ from the hints given (as comments and answers)

$2^{100} \equiv 1 \pmod{125}$

so:

$2^{100k + n} \equiv 2^n \pmod{125}$

for $\pmod{8}$,

$2 \equiv 2, 2^2 \equiv 4, 2^3 \equiv 0, 2^4 \equiv 0.... \pmod{8}$

So I need:

$$\sum_{k=0}^{99} 2^n = 2^{100} - 1$$

$\sum \pmod{1000}$ is what I need to find:

I have the system:

$$2^{100} - 1 \equiv 0 \pmod{125}, 2^{100} - 1 \equiv 7 \pmod{8}$$

Now, I am in trouble, how to solve a congruence system? (Noob to CRT)

Edit: I am attempting to use CRT.

$125r + 8s = 1$ I need to find a $(r, s)$ ordered (integer) pair.

$r = \frac{1 - 8s}{125} \implies 1 - 8s \equiv 0 \pmod{125} \implies 8s \equiv 1 \pmod{125}$

I am not sure how to proceed.

$\endgroup$
  • $\begingroup$ @AndréNicolas Suppose we had $8(5)$ (yes taking a multiple of 5) $=40$. So what is exactly the problem with this? $\endgroup$ – Amad27 Jul 27 '15 at 13:02
  • $\begingroup$ $2^n$ can never be divisible by $5$, so it cannot be congruent to $5$ mod $125$, and therefore cannot be congruent to $40$ mod $1000$. Modulo $125$ it can be anything other than a multiple of $5$. The system does not like long strings of comments. I will delete most of mine and suggest you also do deleting. $\endgroup$ – André Nicolas Jul 27 '15 at 13:09
  • $\begingroup$ @AndréNicolas, done. Okay, that is an interesting method, I would like to know more please. So using your method. $2^{100k +n} \equiv 2^n \pmod{125}$ and $2^{n} \equiv 0 \pmod{8}$. What do you do after this layout? $\endgroup$ – Amad27 Jul 27 '15 at 13:25
  • $\begingroup$ For every $a$ relatively prime to $125$, the congruence $2^n \equiv a\pmod{125}$ has a solution, and therefore for every $b$ divisible by $8$ but not by $5$, the congruence $2^n\equiv b\pmod{1000}$ has a solution. For other $b$ there is no solution. Now note that $b$ is divisible by $8$ but not by $5$ iff $1000-b$ is divisible by $8$ but not by $5$. Now $b$ and $1000-b$ cancel modulo $1000$. It follows that the sum of the numbers between $1$ and $999$ that are congruent to some $2^n$ ($n\ge 3$) is divisible by $1000$. (Basically, a pairing argument.) $\endgroup$ – André Nicolas Jul 27 '15 at 13:56
  • $\begingroup$ @AndréNicolas, wow that is a very complicated solution at my level actually. Do you think you can assist me with summing the powers of $2$ method? That is easier for me? I mean: $2^{102} \equiv 4 \pmod{125}, \equiv 0 \pmod{8}$ hence, $\equiv 504 \pmod{1000}$ is a solution. How do we know if $504$ has ever appeared before or not? What about the powers later on? $\endgroup$ – Amad27 Jul 27 '15 at 14:11
3
$\begingroup$

Continuing vadim123's answer, we have that $n\geq 3$ implies $2^n\equiv 0\pmod{8}$. The subgroup generated by $2$ in $\mathbb{Z}_{/125\mathbb{Z}}^*$ is the whole $\mathbb{Z}_{/125\mathbb{Z}}^*$, since: $$ \left|\mathbb{Z}_{/125\mathbb{Z}}^*\right|=100,\quad 2^{50}\equiv -1\pmod{125},\quad 2^{20}\equiv 76\pmod{125} $$ so a power of two $\pmod{125}$ is allowed but be anything but a multiple of five. So for any $n\geq 3$, $2^{n}\pmod{1000}$ is a multiple of eigth but not a multiple of five. No further restrictions. Then we just have to compute:

$$\left(2^0+2^1+2^2\right)+\left(2^{3}+2^4+\ldots+2^{102}\right)\pmod{1000}$$ since that sum accounts for every possible remainder. The previous line is $\equiv 7\pmod{8}$ and $7\pmod{125}$, hence the answer is simply $\color{red}{7}$.

$\endgroup$
  • $\begingroup$ (+1) tricky notation, no clue of some of these but I'll try to understand the best. Why cant it be a multiple of $5$? is it because if $x = 5y$ then $x \equiv 0 \pmod{125}$, but that isnt necesarily true though. ? $\endgroup$ – Amad27 Jul 26 '15 at 19:22
  • $\begingroup$ $2$ and $5^3$ are coprime, hence $gcd(2^n,5^3)=1$ for any $n\geq 0$. $\endgroup$ – Jack D'Aurizio Jul 26 '15 at 19:24
  • $\begingroup$ Yes I saw that because of Euler's theorem, but that doesnt imply anything about divisibility by $5$ though? $\endgroup$ – Amad27 Jul 26 '15 at 19:25
  • $\begingroup$ @Amad27: that is really trivial. If $2^n = 125a+5b$, $5$ divides $2^n$. That cannot happen. $\endgroup$ – Jack D'Aurizio Jul 26 '15 at 19:26
  • $\begingroup$ alright so far so good. Now the tricky part is $2^{100}, 2^{101}, 2^{102}$. I stopped at $2^{99}$ since $\pmod{125}$ it cycles after $2^{100}$ so $2^{102} \equiv 4 \pmod{125}$ and we already counted that? $\endgroup$ – Amad27 Jul 26 '15 at 19:27
3
$\begingroup$

If $2^i\equiv 2^j\pmod{1000}$, then $2^i\equiv 2^j\pmod{125}$ and $2^i\equiv 2^j\pmod{8}$. But the latter holds for all $i,j$ that are at least $3$. So instead focus on the former. It turns out that the order of $2$, mod $125$, is $100$. That is, $2^{100}\equiv 1\pmod{125}$, but not for any smaller positive (integer) power.

$\endgroup$
  • $\begingroup$ (+1), but how would I use this idea though? $\endgroup$ – Amad27 Jul 26 '15 at 18:38
  • 1
    $\begingroup$ You asked for hints only; this is a hint. $\endgroup$ – vadim123 Jul 26 '15 at 19:07
  • $\begingroup$ Thanks. It helped alot (Euler's theorem etc..) very helpful. $\endgroup$ – Amad27 Jul 26 '15 at 19:25

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.