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.