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

\[\begin{equation*} N = \sum_{k=0}^n a_k 10^k. \end{equation*}\]

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

\[\begin{equation*} N \equiv \sum_{k=0}^n a_k \mod 3. \end{equation*}\]

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

\[\begin{equation*} N \equiv \sum_{k=0}^n (-1)^k a_k \mod 11. \end{equation*}\]

This \(N\) is divisible by \(11\) if and only if the alternating sum of its digits is divisible by \(11\).