The Digit-Sum Test for Divisibility by 9
Let $a$ be a positive integer with decimal digits $a_n a_{n-1} \cdots a_1 a_0$, so that $a = \sum_{k=0}^{n} a_k 10^k$ with each $a_k \in \{0, 1, \ldots, 9\}$.
(a) State a simple test, based only on the digits of $a$, for deciding whether $a$ is divisible by $9$.
(b) Prove that the test is correct.
(c) Explain why the same test also works for divisibility by $3$, and why it does not work for divisibility by $7$.
Hints
- Try a few examples: $18, 27, 36, \ldots, 99, 108, 117$. What do the digits of multiples of 9 have in common?
- Write $a = \sum a_k 10^k$ and compare it with the digit sum $\sum a_k$. Their difference is $\sum a_k (10^k - 1)$.
- Every number of the form $10^k - 1 = 99\cdots9$ is a multiple of $9$. Equivalently $10 \equiv 1 \pmod 9$, so $10^k \equiv 1 \pmod 9$ and $a \equiv \sum a_k \pmod 9$.
Worked Solution
How to Think About It: A divisibility test based on digits must come from the behaviour of powers of $10$ modulo the divisor. If $10^k$ leaves remainder $1$ for every $k$, the number reduces to its digit sum modulo that divisor.
Quick Estimate: $10 = 9 + 1$, $100 = 99 + 1$, $1000 = 999 + 1$: every power of ten is one more than a multiple of nine. So stripping the "$-1$" from each power of ten leaves only the digits, which is why the digit sum controls divisibility by $9$.
Formal Solution:
Part (a): The test. An integer is divisible by $9$ if and only if the sum of its decimal digits is divisible by $9$. (Apply the test repeatedly if the digit sum is still large: $a$ is divisible by $9$ iff its digital root is $9$.)
Part (b): Proof.
*Step 1 -- Powers of ten modulo 9.* Since $10 = 9 + 1$, we have $10 \equiv 1 \pmod 9$. Multiplying this congruence by itself $k$ times gives $10^k \equiv 1^k = 1 \pmod 9$ for every $k \ge 0$. Equivalently, $10^k - 1 = 9 \times \underbrace{11\cdots1}_{k}$ is a multiple of $9$.
*Step 2 -- Compare the number with its digit sum.* Let $S = \sum_{k=0}^{n} a_k$ be the digit sum. Then $$a - S = \sum_{k=0}^{n} a_k 10^k - \sum_{k=0}^{n} a_k = \sum_{k=0}^{n} a_k \left(10^k - 1\right).$$ Each term $a_k (10^k - 1)$ is a multiple of $9$ by Step 1, so $a - S$ is a multiple of $9$; that is, $a \equiv S \pmod 9$.
*Step 3 -- Conclude.* Since $a$ and $S$ differ by a multiple of $9$, $9 \mid a$ if and only if $9 \mid S$. This proves both directions of the test. (Numerically, the equivalence checks out for every integer up to $200{,}000$.)
Part (c): Other divisors.
For $3$: the same argument works because $10 \equiv 1 \pmod 3$ as well, so $a \equiv S \pmod 3$ and $3 \mid a$ iff $3 \mid S$. In fact $a \equiv S$ modulo any divisor of $9$.
For $7$: $10 \equiv 3 \pmod 7$, and the powers of $10$ cycle through $1, 3, 2, 6, 4, 5$ modulo $7$, never staying at $1$. So $a \equiv \sum a_k 3^k \pmod 7$, which is not the digit sum. Concrete counterexample: $7$ itself is divisible by $7$ but its digit sum is $7$, while $16$ has digit sum $7$ and is not divisible by $7$. A working test for $7$ must weight the digits by the residues $1, 3, 2, 6, 4, 5, \ldots$ (or use the "double the last digit and subtract" rule, which is the same idea in disguise).
Answer: (a) $a$ is divisible by $9$ iff its digit sum is divisible by $9$. (b) Because $10^k \equiv 1 \pmod 9$ for all $k$, $a - \sum a_k = \sum a_k (10^k - 1)$ is a multiple of $9$, so $a \equiv \sum a_k \pmod 9$. (c) The proof only needs $10 \equiv 1$ modulo the divisor, which holds for $3$ and $9$ but not for $7$ (where $10 \equiv 3$).
Intuition
The whole result is the single congruence $10 \equiv 1 \pmod 9$: raising both sides to the $k$-th power shows every power of ten is $1$ modulo $9$, so a number and its digit sum are congruent modulo $9$ and share divisibility by $9$ (and by $3$, since $10 \equiv 1 \pmod 3$ as well). For $7$ the base $10$ is not $1$ modulo $7$, so the digit sum carries no information. Modular arithmetic of this kind is a workhorse for quick sanity checks: "casting out nines" catches most arithmetic slips, and the same reduce-the-base idea drives checksum and hashing schemes.