关于 2, 5, 4, 25

这一类比较显然。对于 $x = 2, 5$ 只需数字最后 $1$ 位能被被 $x$ 整除即可。 对于 $x = 4, 25$ 只需数字最后 $2$ 位能被整除即可。

之所以我们可以进行截断，是因为 $10 \equiv 0 \ (\bmod 2\ )$, $10 \equiv 0 \ (\bmod 5\ )$ 而 $100 \equiv 0 \ (\bmod 4\ )$, $100 \equiv 0 \ (\bmod 25\ )$。

更一般的，由于 $10 = 2 \times 5$，所以十进制下，采用这种利用某些低位判断整个数字是否能被 $x$ 整除，只适用于 $x = 2 ^ a \cdot 5 ^ b$ 的形式，且需要截取较小的 $\max(a, b)$ 位。

对于 $b$ 进制数，显然我们也可以质因数分解 $b$ 然后推广这个性质。

关于 3, 9

这一类数一般的判断方法是各位数字的和可以被 $x$ 整除，则其可以被 $x$ 整除。

真正的原因是 $10 \equiv 1 \ (\bmod 3\ )$, $10 \equiv 1 \ (\bmod 9\ )$。

更进一步的。$10^k \equiv 1 \ (\bmod 3\ )$, $10^k \equiv 1 \ (\bmod 9\ )$。

于是对于数 $n = a0 + a1 \cdot 10 + a2 \cdot 10^2 + \cdots + a_m \cdot 10^m$ 有：

注意到 $3, 9$ 是唯二符合这个规律的数字。（$x > 10$ 则 $10 \bmod x = 10$）

但其实我们也可以一定程度放宽这样的限制，比如将每 $k$ 位加起来。 这样其实我们需要的是对于 $x$ 有

当 $k = 2$ 有 $11, 33, 99$。

当 $k = 3$ 有 $27, 37, 111, 333, 999$。

显然的，对于 $3 ^ k$ 总有 $ 10^k \equiv 1 \ (\bmod 3 ^ k\ ) $

关于 7

$7$ 有两种主要的判断方式。

方法一：交替和法

从低向高每 $3$ 位一组做正负交替的和，如果结果能被 $7$ 整除则能被 $7$ 整除。

例如数字 $12,345,676$，从低向高 $3$ 位一组的和是 $+12 - 345 + 676 = 343 = 49 \times 7$，而 $12,345,676 = 1,763,668 \times 7$。

底层逻辑是 $ 1000 \equiv 6 \equiv -1 \ (\bmod 7 \ )$，而 $1,000,000 \equiv 1 \ (\bmod 7 \ )$

注意到，总有 $(n - 1) ^ 2 \equiv 1 \ (\bmod n\ )$，所以对于任意 $x$ 如果我们能找到 $10 ^ k \equiv (x - 1) \ (\bmod x\ )$，则我们就可以每 $k$ 位分一组。

方法二：去除末位法

对于编程来说这个方法意义不大，因为我们总有一般化的方法。直接从高位开始，结论也更显然。

sum = 0
for i = n - 1 -> 0
  sum = (sum * 10 + a[i]) % x

对于 $7$ 我们可以这样做将去掉末尾的数减去，末位乘 $2$。如果新数可以被 $7$ 整除，则原数可以被 $7$ 整除。

例如 $12,345,676$ -> $1,234,567 - 12 = 1,234,555$ -> $123,455 - 10 = 123,445$ -> $12,344 - 10 = 12,334$ -> $1,233 - 8 = 1,225$ -> $122 - 10 = 112$ -> $11 - 4 = 7$ 可以整除。

为什么这是对的？

$10 \equiv 3 \ (\bmod \ 7)$ 又有 $3 x 5 \equiv 1 \ (\bmod 7\ )$ 所以我们可以得出：

若 $n = a0 + a1 * 10$ 且 $n \equiv 0 \ (\bmod 7\ )$，则由 $(5, 7) = 1$

则

即

所以这种方法的核心是，对于 $x$ 找到一个与其互质的数 $y$ 且 $10y \equiv 1 \ (\bmod x\ )$，这样每次只需减掉末位 $a0 * (x - y)$ 即可。（这里注意 y > x 是没有意义的，因为如果这样的 $y$ 存在，则 $y \bmod x$ 一定也合法）

例如对于 $x = 11$ 显然 $y = 10$ 时 $100 \equiv 1 \ (\bmod 11\ )$，则规则为，递归的减去最后一位（的 $11 - 10 = 1$ 倍）即可。