Rule of nines (mathematics)

From Wikipedia, the free encyclopedia

The rule of nines, in mathematics, is a divisibility rule for the divisor 9. It is notable because it illustrates some interesting properties of modular arithmetic, and its proof is derived from that basis. The rule is that any positive integer is divisible by 9 if and only if the sum of its digits is also divisible by 9.

[edit] Proof

This proof, although not directly taken from that source, is based on the one by Flannery (2001).

Let the positive integer n be represented by the decimal digits a_k a_k-1 ... a₂ a₁ a₀. Because

$\begin{align} 10^0 &\equiv 1 \pmod{9} \\ 10^1 &\equiv 1 \pmod{9} \\ 10^2 &\equiv 1 \pmod{9} \\ &... \end{align}$

and multiplication functions the same way in modular arithmetic as it does in elementary algebra,^[1]

$\begin{align} a_0 \times 10^0 &\equiv a_0 \pmod{9} \\ a_1 \times 10^1 &\equiv a_1 \pmod{9} \\ a_2 \times 10^2 &\equiv a_2 \pmod{9} \\ &... \\ a_k \times 10^k &\equiv a_k \pmod{9}. \end{align}$

Summing these equivalences, we get

$a_k \times 10^k + ... + a_0 \times 10^0 \equiv a_k + ... + a_0 \pmod{9}.$

Notice that the left term of this equivalence is equal to n, according to our definition. Therefore, the sum of the digits of n is equivalent to n itself (modulo 9); and so this sum is divisible by 9 if and only if n is also divisible by 9. The proof is complete.