1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Euler's totient theorem repeated use. $\endgroup$ – Roddy MacPhee Sep 26 at 21:36
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.