a) Determine a criterion for divisibility by 7, and use it to determine the remainder of the number $12345678923$ when divided by 7.
b) Assume $a≡b(\mod m)$. If $r≡s(\mod m)$ is it true that $ar≡bs(\mod m)$ ? Either prove or give a counterexample.
c) Evaluate the remainder of $12345678923^{128}$ when divided by $7$
d) What are the last two digits (rightmost digits) of the number $9^{9^{9^9}}$?
a) Consider the number
$$\color{green}{12345678923}=\color{orange}{10^{10}}\color{green}{1}+\dots+\color{orange}{10^0}\color{green}{3}$$
Apply ii) of the following Theorem to get the $\color{red}{red}$ part
If $a\equiv b(\text{mod }m)$ and $c\equiv d(\text{mod }m)$, then
$i)(a+c)\equiv(b+d)(\text{mod }m)$
$ii)ac\equiv bd(\text{mod }m)$
$$\color{orange}{10^0}\equiv1\mod7\wedge \color{green}{3}\equiv\color{blue}{3}\mod7$$ Since $1(3)\equiv\color{red}{3}\mod7$ $$\color{orange}{10^1}\equiv\color{red}{3}\mod7\wedge \color{green}{2}\equiv\color{blue}{2}\mod7$$ Since $3(3)\equiv\color{red}{2}\mod7$ $$\color{orange}{10^2}\equiv\color{red}{2}\mod7\wedge \color{green}{9}\equiv\color{blue}{2}\mod7$$ Since $2(3)\equiv\color{red}{-1}\mod7$ $$\color{orange}{10^3}\equiv\color{red}{-1}\mod7\wedge \color{green}{8}\equiv\color{blue}{1}\mod7$$ Since $-1(3)\equiv\color{red}{-3}\mod7$ $$\color{orange}{10^4}\equiv\color{red}{-3}\mod7\wedge \color{green}{7}\equiv\color{blue}{0}\mod7$$ Since $-3(3)\equiv\color{red}{-2}\mod7$ $$\color{orange}{10^5}\equiv\color{red}{-2}\mod7\wedge \color{green}{6}\equiv\color{blue}{6}\mod7$$ $$\vdots$$
Then apply i) and ii) to get
$$\color{green}{12345678923}\equiv 1(\color{blue}{3})+\color{red}{3}(\color{blue}{2})+\dots+\color{red}{-3}(\color{blue}{1})\mod7$$
$$\color{green}{12345678923}\equiv 18\mod7$$ Also $$18\equiv4\mod7$$
Apply the following
if $a\equiv b(\text{mod m})$ and $b\equiv c\text{(mod }m)$, then $a\equiv c(\text{mod m})$
Then we have
$$\color{green}{12345678923}\equiv 4\mod7$$
b) This is a easy proof$\dots$it's ii) of first theorem that we just used
Assume $a≡b(\mod m)$ and $r≡s(\mod m)$
Show $ar≡bs(\mod m)$
by assumption that
$$\exists k_1\in\mathbb{N},s.t.a-b=k_1(m)\text{ and }\exists k_2\in\mathbb{N},s.t.r-s=k_2(m)$$ $$\Rightarrow a=b+k_1(m)\text{ and }r=s+k_2(m)$$ $$\Rightarrow ar=(b+k_1m)(s+k_2m)$$ $$\Rightarrow ar=b k_2 m + b s + k_1 k_2 m^2 + k_1 m s$$ $$\Rightarrow ar-bs=m(b k_2 + k_1 k_2 m + k_1s)$$ $$\Rightarrow ar≡bs\mod m\tag*{$\square$}$$
c)Consider the number $$\color{green}{12345678923}^{128}$$
Since $$\color{green}{12345678923}^0\equiv \color{red}{1}\mod7$$
And from a) we know
$$\color{green}{12345678923}^1\equiv \color{red}{4}\mod7$$
It's not a good idea to calculate $4^{128}$ as a reminder
Apply b)$$\color{green}{12345678923}^2\equiv 4^2\mod7$$
Also $$4^2\equiv\color{red}{2}\mod7$$
Apply b)$$\color{green}{12345678923}^3\equiv 2(4)\mod7$$
Also $$2(4)\equiv\color{red}{1}\mod7$$
The reminder is repeating between $1,4,2$
Since at power $\color{blue}{2}$ have reminder $\color{red}{2}$
$$\frac{128-\color{blue}{2}}{3}=42\in\mathbb{Z}$$
$$\Rightarrow \color{green}{12345678923}^{128}\equiv \color{red}{2}\mod7$$
d)$\dots$
For a),b) and c) is there better methods?
How do I evaluate $d)$? (Without calculator)
Any help or hint or suggestion would be appreciated.