各桁の和を足す操作の繰り返しと、9で割った余りは一致する

812

「各桁の和を足して $9$ の倍数になったらその数字は $9$ で割れるんだぜ（ドヤァ）」と言う人はいるのですが、 $\mod 9$ に関しては触れられていないのでここに記述します。

自然数Nに対し
$N$ の各桁を足す操作を $1$ 桁になるまで繰り返すと、 $N \mod 9$ と一致する。

例： $89375 \equiv 5 \mod 9$
$8 + 9 + 3 + 7 + 5 = 32 \to 3 + 2 = 5$

$N = N_{0} = \sum_{i = 0}^{n_{0}} a_{0 i} \times 10^{i}$
$N_{1} = \sum_{i = 0}^{n_{0}} a_{0 i} = \sum_{i = 0}^{n_{1}} a_{1 i} \times 10^{i}$
$. . .$
$N_{k} = \sum_{i = 0}^{n_{k - 1}} a_{(k - 1) i} = \sum_{i = 0}^{n_{k}} a_{k i} \times 10^{i}$
$. . .$
$N_{m} = \sum_{i = 0}^{n_{m - 1}} a_{(m - 1) i} = a_{m 0} (n_{i}, k, m は自然数)$
とする。
以下、数学的帰納法により証明する。
$(Ⅰ) k = 0$
$N_{0} \mod 9 \equiv N \mod 9$

$(Ⅱ) k = l のとき、 N_{l} \mod 9 \equiv N \mod 9 と仮定すると、$
$k = l + 1 のとき$
$N_{l} - N_{l + 1} = \sum_{i = 0}^{n_{l}} a_{l i} \times 10^{i} - \sum_{i = 0}^{n_{l}} a_{l i}$
$= \sum_{i = 0}^{n_{l}} a_{l i} \times (10^{i} - 1)$
$= \sum_{i = 1}^{n_{l}} a_{l i} \times (10^{i} - 1)$
$= \sum_{i = 1}^{n_{l}} a_{l i} \times (10 - 1) (10^{i - 1} + 10^{i - 2} + . . . + 1)$
$= 9 \sum_{i = 1}^{n_{l}} a_{l i} \times (10^{i - 1} + 10^{i - 2} + . . . + 1)$
$N_{l} - N_{l + 1} は 9 の倍数$
$N_{l} \mod 9 \equiv N \mod 9$ 　かつ　 $N_{l} - N_{l + 1} \equiv 0 \mod 9 より$
$N_{l + 1} \mod 9 \equiv N_{l} \mod 9 \equiv N \mod 9$
数学的帰納法より
$\forall k, N_{k} \mod 9 \equiv N \mod 9$
$特に k = m のとき、 N_{m} \mod 9 \equiv N \mod 9$