Theorem 5.2.5.1.
A positive integer is congruent to the sum of its decimal digits modulo \(9\text{.}\)
Subsection 5.2.5 Casting out nines
Proof.
Consider the decimal (base 10) expansion of \(a\text{:}\)
\begin{equation*}
a=\sum_{i=0}^n a_i 10^i
\end{equation*}
Then the base 10 representation of \(a\) is \(a=(a_n \dots a_1 a_0)\text{.}\) We take both sides modulo 9 and obtain.
\begin{align*}
a \bmod 9 \amp = \left(\sum_{i=0}^n a_i 10^i\right) \bmod 9 \\
\amp = \left(\sum_{i=0}^n a_i (10\bmod 9)^i\right) \bmod 9
\end{align*}
Because \(10\bmod 9=1\) we have
\begin{align*}
a \bmod 9
\amp= \left(\sum_{i=0}^n a_i 1^i\right)\bmod 9\\\\
\amp= \left(\sum_{i=0}^n a_i\right)\bmod 9.
\end{align*}
Which means that \(\displaystyle a\equiv \left(\sum_{i=0}^n a_i\right)\pmod{9}\text{.}\)
Remark 5.2.5.2.
This result is the reason the casting out nines technique for checking arithmetic works. See the video Casting Out Nines by Numberphile for additional details.
1
youtu.be/FlndIiQa20oSince an integer is divisible by \(9\) if and only if it is congruent to \(0\) modulo \(9\text{,}\) Theorem 5.2.5.1 gives the following divisibility criterion.
Corollary 5.2.5.3. Divisibility by nine.
A natural number is divisible by \(9\) if and only if the sum of its decimal digits is divisible by \(9\text{.}\)
Proof.
Let \(a\in\NN\text{.}\) By Theorem 5.2.5.1 we know \(a\) is congruent to the sum of its decimal digits modulo \(9\text{.}\) Thus \(a\) is congruent to \(0\) modulo \(9\) if and only if the sum of its decimal is congruent to \(0\) modulo \(9\text{.}\) That is, \(a\) is divisible by \(9\) if and only if the sum of its decimal digits is divisible by \(9\text{.}\)
