9(および3)による整除の桁和判定法

ステップ1. すべての $i\ge0$ に対して $10^i \equiv 1 \pmod 9$ であることを帰納法で示す。基底段階 $i=0$：$10^0=1\equiv1\pmod9$。帰納段階：$10^i\equiv1\pmod9$ ならば、$10^{i+1}=10\cdot10^i\equiv10\cdot1=10\equiv1\pmod9$（$10 \equiv 1 \pmod 9$ を用いる）。よってすべての $i$ で $10^i\equiv1\pmod9$。

ステップ2. 位取り展開に代入する:$n=\sum_i d_i 10^i \equiv \sum_i d_i\cdot1 = \sum_i d_i \pmod9$。よって $n$ とその桁の和は、$9$ で割ると常に同じ余りを持つ。

ステップ3. 結論:$9\mid n$ となるのはまさに $n\equiv0\pmod9$ のときであり、ステップ2により、これはまさに $\sum_i d_i\equiv0\pmod9$ のとき、すなわち $9$ が桁の和を割り切るときに起こる。$9=3\times3$ であり、同じ合同式 $10\equiv1\pmod3$ も成り立つので、$9$ の代わりに $3$ を用いた同一の議論全体が、$3$ による整除性の版を証明する。