整除、因数与倍数

$10$ 的任何幂除以 $9$ 余数都是 $1$(因为 $10=9+1$),所以把某个数字移到更高的数位,并不会改变它模 $9$ 的贡献——整个数同余于其数字的简单之和。

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

与 $9$ 不同,$10$ 的幂在模 $11$ 下不会保持同余于 $1$——因为 $10$ 本身模 $11$ 同余于 $-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}$。

第二步。代入位值展开式:$n=\sum_i d_i10^i \equiv \sum_i d_i(-1)^i \pmod{11}$,这恰好是交替数字和 $\sum_i (-1)^i d_i$。

第三步。得出结论:$11\mid n$ 当且仅当 $n\equiv0\pmod{11}$,由第二步这恰好等价于 $11$ 整除 $\sum_i (-1)^i d_i$。