倍数の判定法

正の整数 $N$ の 10 進表示を $N=\sum_{i=0}^kd_i10^i$（$0\le d_i\le9$）とする。

1. $N\equiv\sum_id_i\pmod9$。したがって $9$（および $3$）で割り切れるための必要十分条件は、各位の数字の和が $9$（$3$）で割り切れること。
2. $N\equiv\sum_i(-1)^id_i\pmod{11}$。$11$ で割り切れるのは、交代和 $d_0-d_1+d_2-\cdots$ が $11$ で割り切れるとき。
3. $N$ を下から 3 桁ずつの組 $g_0,g_1,\dots$ に分けて $N=\sum_jg_j1000^j$ とすると、$N\equiv\sum_j(-1)^jg_j\pmod{1001}$。$1001=7\cdot11\cdot13$ なので、$N$ が $7$ や $11$ や $13$ で割り切れるかは、この交代和でも判定できる。
4. $N$ を $2^e$ や $5^e$（$e\le k+1$）で割った余りは、下 $e$ 桁の数で決まる。とくに $4$ で割り切れるかは下 2 桁、$8$ で割り切れるかは下 3 桁で決まる。