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.
Best Answer
Part (a) is simpler to group digits 3 at a time, using $1000 ≡ -1 \bmod 7$
$$12,345,678,923 ≡ 923-678+345-12 ≡ 578 ≡ 501 ≡ 5(2)+1≡ 4\bmod 7$$
Part (b), modulo $m$, with $a≡b, r≡s$. Assume $ar \not\equiv bs$, we have:
$$ar-bs ≡ r(a-b) ≡ a(r-s) \not\equiv 0 \bmod m$$ $$→ a \not\equiv b \bmod m \text{, and } r \not\equiv s \bmod m$$ Thus, assumption were wrong, we have $\;ar ≡ bs \bmod m$
Part (c), use $\;4^6 \bmod 7 ≡ 1$
$$12345678923^{128} ≡ 4^{6\times21+2} ≡ 4^{2} ≡ 16 ≡ 2 \bmod 7$$
Part (d)
$9^{2} \bmod 100 ≡ 81$
$9^{4} \bmod 100 ≡ 81^2 ≡ 6561 ≡ 61$
$9^{9} \bmod 100 ≡ 61^2\times 9 ≡ 89$
$9^{10} \bmod 100 ≡ 89 \times 9 ≡ 801 ≡ 1$
$$9^{9^9} \bmod 100 ≡ 9^{10k+9} ≡ 9^9 ≡ 89$$ $$9^{9^{9^9}} \bmod 100 ≡ 9^{10k'+9} ≡ 9^9 ≡ 89$$