modular arithmetic

$x\equiv y \pmod z$ — “ $x$ is congruent to $y$ modulo $z$ ” — means that $x$ divided by $z$ gives the same remainder as $y$ divided by $z$ .
i.e. $73\equiv 10 \pmod 7$ , because $73=7\times10+3$ and $10=1\times7+3.$

If $a=b+c$ then

$a^k=(b+c)^k\equiv c^k \pmod b$

Problem: Show that an integer is divisible by $9$ if and only if the sum of its digits is divisible by $9$ .
Solution: Call the digits of the integer $n$ from left to right $a_h,a_{h-1},\cdots ,a_0.$
$10^k=(9+1)^k\equiv 1^k \pmod 9$ , so

$n=\sum_{k=0}^h a_k 10^k\equiv\sum_{k=0}^h a_k \pmod 9.$

i.e. $n$ is divisible by $9$ exactly when the sum of its digits are.