# Sum of remainders of $2^n$

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.

• @AndréNicolas Suppose we had $8(5)$ (yes taking a multiple of 5) $=40$. So what is exactly the problem with this? – Amad27 Jul 27 '15 at 13:02
• $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. – André Nicolas Jul 27 '15 at 13:09
• @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? – Amad27 Jul 27 '15 at 13:25
• 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.) – André Nicolas Jul 27 '15 at 13:56
• @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? – Amad27 Jul 27 '15 at 14:11

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

• (+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. ? – Amad27 Jul 26 '15 at 19:22
• $2$ and $5^3$ are coprime, hence $gcd(2^n,5^3)=1$ for any $n\geq 0$. – Jack D'Aurizio Jul 26 '15 at 19:24
• Yes I saw that because of Euler's theorem, but that doesnt imply anything about divisibility by $5$ though? – Amad27 Jul 26 '15 at 19:25
• @Amad27: that is really trivial. If $2^n = 125a+5b$, $5$ divides $2^n$. That cannot happen. – Jack D'Aurizio Jul 26 '15 at 19:26
• 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? – Amad27 Jul 26 '15 at 19:27

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.

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