判断整除 9(与 3)的数字和法则

第一步。用归纳法证明对一切 $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$。

第二步。代入位值展开式:$n=\sum_i d_i 10^i \equiv \sum_i d_i\cdot1 = \sum_i d_i \pmod9$。因此 $n$ 与其数字和除以 $9$ 总是余数相同。

第三步。得出结论:$9\mid n$ 当且仅当 $n\equiv0\pmod9$,由第二步这恰好等价于 $\sum_i d_i\equiv0\pmod9$,即 $9$ 整除数字和。由于 $9=3\times3$ 且同样的同余式 $10\equiv1\pmod3$ 也成立,把上述论证中的 $9$ 全部换成 $3$,同样证明了整除 $3$ 的版本。