Divisibility rule

A divisibility rule tests whether one integer divides another by replacing it with a simpler equivalent condition. For a base-$b$ expansion $N={\sum }_i{d}_i{b}^i$, the congruence class of $b$ modulo the candidate divisor determines a rule.

In base ten, $10\equiv 1(\mathrm{mod}9)$, so $N$ and its digit sum have the same residue modulo nine. Also $10\equiv -1(\mathrm{mod}11)$, so divisibility by eleven is equivalent to divisibility of the alternating digit sum. For example, $121$ passes because $1-2+1=0$. These tests follow from modular arithmetic and depend on the numerical base.

For a nonnegative integer with decimal expansion $a={\sum }_i{a}_{i}10^i$, the congruence $10\equiv 1(\mathrm{mod}d)$ gives $a\equiv {\sum }_i{a}_i(\mathrm{mod}d)$ whenever $d\mid 9$. Thus divisibility by three or nine is equivalent to divisibility of the sum of its decimal digits by the same number. More generally a base-$b$ expansion has the analogous rule for every divisor of $b-1$. This follows by repeated addition and multiplication in modular arithmetic; it does not require an empirical rule about decimal notation.