各桁の和を足す操作の繰り返しと、9で割った余りは一致する
「各桁の和を足して$9$の倍数になったらその数字は$9$で割れるんだぜ（ドヤァ）」と言う人はいるのですが、$\mod{9}$ に関しては触れられていないのでここに記述します。
自然数Nに対し
$N$の各桁を足す操作を$1$桁になるまで繰り返すと、$N \mod 9$と一致する。
例：$89375 ≡ 5 \mod{9}$
$8+9+3+7+5=32 → 3+2=5$
$N = N_0 = \sum_{i=0}^{n_0}a_{0i}×10^i$
$N_1 = \sum_{i=0}^{n_0}a_{0i} = \sum_{i=0}^{n_1}a_{1i}×10^i$
$...$
$N_k = \sum_{i=0}^{n_{k-1}}a_{(k-1)i} = \sum_{i=0}^{n_k}a_{ki}×10^i$
$...$
$N_m = \sum_{i=0}^{n_{m-1}}a_{(m-1)i}=a_{m0} (n_i,k,mは自然数)$
とする。
以下、数学的帰納法により証明する。
$(Ⅰ) k=0$
$N_0 \mod{9} ≡ N \mod{9}$
$(Ⅱ) k=l のとき、N_l \mod{9} ≡ N \mod{9} と仮定すると、$
$k=l+1のとき$
$N_l-N_{l+1}=\sum_{i=0}^{n_l}a_{li}×10^i-\sum_{i=0}^{n_{l}}a_{li}$
$=\sum_{i=0}^{n_l}a_{li}×(10^i-1)$
$=\sum_{i=1}^{n_l}a_{li}×(10^i-1)$
$=\sum_{i=1}^{n_l}a_{li}×(10-1)(10^{i-1}+10^{i-2}+...+1)$
$=9\sum_{i=1}^{n_l}a_{li}×(10^{i-1}+10^{i-2}+...+1)$
$N_l-N_{l+1} は9の倍数$
$N_l \mod{9} ≡ N \mod{9}$ かつ $N_l-N_{l+1} ≡ 0 \mod{9} より$
$N_{l+1} \mod{9} ≡ N_l \mod{9} ≡ N \mod{9}$
数学的帰納法より
$∀k, N_{k} \mod{9} ≡ N \mod{9}$
$特にk=mのとき、N_{m} \mod{9} ≡ N \mod{9}$
ちなみに$N_m＝0$ということは$N$が$9$で割れるということと同じです。
まとめ
これからは
「各桁の和を足していったときの$9$で割った余りとその数字を$9$で割った余りは同じなんだぜ（ドヤァ）」と言いましょう。