Advanced Modular Arithmetic #3

Note that $112=1110000_{(2)}=2^6+2^5+2^4=2^4(2^2+2+1)=2^4(2^3-1)\equiv2^4(2^3-1)(2^3+1)\equiv2^{10}-2^4\equiv0\pmod{112}$ .

Then we can know that $2^{10}\equiv2^4\pmod{112}$ .

Therefore, for positive integers $n$ and $k\geq4$ , $\boxed{2^{6n+k}\equiv2^k\pmod{112}}$ .

Then, $2^{111111111}=2^{6p+3}=2^{6(p-1)+9}\equiv2^9\equiv64\pmod{112}$ .

$\therefore\boxed{R_1=64}$ .

---

Note that $189=10111101_{(2)}=2^7+2^5+2^4+2^3+2^2+1$ .

See the picture above. Top line is how many powers of $2$ each column represents.

Now look at column $6$ . It is left out with two $1$ 's, which means it is equal to $2^6+2^6=2^7$ .

Then we can see that we add an invisible $1$ to column $7$ , and now the strangeness of column $7$ is also explained.

(Think of advancing more up in basic additions, where $14+26=(1+2)\times10+(4+6)=(1+2+1)\times10$ .)

You'll see that even though column $18$ is blank, it will be filled by two $2^{17}$ 's.

Therefore,

$2^7+2^5+2^4+2^3+2^2+1\equiv(2^7+2^5+2^4+2^3+2^2+1)(2^{10}+2^9-2^7-2^5+2^3+2^2-1)\equiv2^{18}-1\equiv0\pmod{189}$ .

So, for non-negative integer $n\geq1$ and $p$ , $2^{18n+p}\equiv2^p\pmod{189}$ .

Then, $2^{111111111}=2^{18\times6172839+9}\equiv2^9\equiv134\pmod{189}$ .

$\therefore\boxed{R_2=134}$ .

---

Note that $262657=1000000001000000001_{(2)}=2^{18}+2^9+1\equiv(2^9-1)(2^{18}+2^9+1)\equiv2^{27}-1\equiv0\pmod{262657}$

Then, for non-negative integer $n\geq1$ and $p$ , $2^{27n+p}\equiv2^p\pmod{262657}$ .

Then, $2^{111111111}=2^{27\times4115226+9}\equiv2^9\equiv512\pmod{262657}$ .

$\therefore\boxed{R_3=512}$ .

---

Therefore, $R_1+R_2+R_3=64+134+512=\boxed{710}$ .