divisibility by 9

If the sum of the digits of a number is divisble by 9, then the number is divisible by nine. Consider a number with decimal representation \(a_n a_{n-1} \cdots a_0\). This can be written as \(a_n\cdot (9+1)^n + a_{n_1}\cdot(9+1)^{n-1} + \cdots + a_0 (9 + 1)^0\). Consider one of the terms \(a_k (9+1)^k\). After expanding \((9+1)^k\), we will get a sum of terms that are powers of 9 and we will get a single term that is \(1\). So, dropping out all terms that are multiplied by a power of nine from our decimal expansion, we are left with the remainder \(a_n + a_{n-1} \cdots + a_0\). And if this sum is divisible by 9, then the whole number is divisble by 9.

This can also be used to show that if a number has digits that sum to a number divisible by 3 then it is divisible by 3 because \((9+1)^k = (3^2 + 1)^k\).