Determine remainders of large numbers

Question

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.

Answer 1

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