# Determine remainders of large numbers

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.

• Euler's totient theorem repeated use. – user645636 Sep 26 '19 at 21:36

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