Skip to main content
1 of 2
albert chan
  • 2.2k
  • 8
  • 10

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^{89} ≡ 9^9 ≡ 89$$

albert chan
  • 2.2k
  • 8
  • 10