## Tuesday, November 12, 2013

### Simple Divisibility Tests

In this post we will justify some common divisibility tests that most school children are familiar with. Recall that a number such as $111$ is divisible by $3$ if and only if the sum of the digits is divisible by $3$. Since $1+1+1=3$ is divisible by $3$, we see that $111$ is divisible by three.

More generally, an integer $N$ is divisible by $3$ if and only if the sum of the digits appearing in $N$ is divisible by $3$.

This can be proven quite easily using modular arithmetic. Recall that an integer $N$ with decimal expansion $N=a_n a_{n-1} \dots a_1 a_0$ can be written as $N = \sum_{k=0}^n a_k 10^k.$ Here $a_k \in \{ 0, 1, \dots, 9 \}$ for each $k=1, \dots, n$. Since $10^k \equiv 1 \mod 3$ for any natural number $k$, we see that $N \equiv \sum_{k=0}^n a_k \mod 3.$ This proves the claim.

Since $10^k \equiv 1 \mod 9$ for each natural number $k$, the same divisibility test holds for $9$ as well. That is, a number $N$ is divisible by $9$ if and only if the sum of its digits is divisible by $9$.

A similar observation gives a divisibility test for $11$. Note that $10^k \equiv (-1)^k \mod 11$ for any natural number $k$, so $N = a_n \dots a_0$ satisfies $N \equiv \sum_{k=0}^n (-1)^k a_k \mod 11.$ This $N$ is divisible by $11$ if and only if the alternating sum of its digits is divisible by $11$.