整除性、約数と倍数

$10$ のどのべき乗も $9$ で割ると余り $1$ になる（$10=9+1$ だから）ので、ある桁を上位の位に移しても、法 $9$ でのその寄与は決して変わらない——数全体は、その桁の単純な和と合同である。

ステップ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$ による整除性の版を証明する。

$9$ とは異なり、$10$ のべき乗は法 $11$ で $1$ に合同のままではない——$10$ 自体が法 $11$ で $-1$ に合同であるため、一段ごとに符号が反転する。偶数位の桁は通常どおり寄与し、奇数位の桁は負に寄与する。

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

ステップ2. 位取り展開に代入する:$n=\sum_i d_i10^i \equiv \sum_i d_i(-1)^i \pmod{11}$、これはまさに交代和 $\sum_i (-1)^i d_i$ である。

ステップ3. 結論:$11\mid n$ となるのはまさに $n\equiv0\pmod{11}$ のときであり、ステップ2により、これはまさに $11$ が $\sum_i (-1)^i d_i$ を割り切るときに起こる。