整除规则

整除是數學中兩自然數間一種關係。自然數甲可被自然數乙整除，是指乙是甲的因數，且甲是乙的整數倍數，也就是甲除以乙沒有餘數。下面列出了十進位中判斷整數除以另一整數的商為整數，且餘數為零的一些規則。

## 基本判別

* 0：所有非 0 的整數之倍數。
* ±1：所有整數之因數。

## 可於最後幾位判別

2 和 5 都是 10 的因數，在十進位判別是否有 $2^{k}$ 或 $5^{k}$ 的因數只須**取其最後 k 位，除以 $2^{k}$ 或 $5^{k}$ ，可除盡即是**：

* ±2：所有偶數（0、2、4、6、8 結尾）皆有此因數。如 2、−6、989896、11111112、−454
* ±4：最後兩位數可以被 4 除盡，即是。如 98989898985**40**→40/4＝10
* ±8：若最後三位數可以被 8 除盡，即是。如 8000、1256000、95872
* ±5：查看最後一位數。如果可以被 5 除盡（為 0 或 5），即是。如 5454545、45454500、50－
* ±10：看最後一位數為 0（即末兩位為 10 的整倍數）即是。如 530、73500、50
* ± $2^{n}$ ：最後 n 位數可以被 $2^{n}$ 除盡。
* ± $5^{n}$ ：最後 n 位數可以被 $5^{n}$ 除盡。
* ± $10^{n}$ ：最後 n 位數字都全部是 0。

上面的性質亦可推廣到求餘數： 
 $\sum _{r=0}^{n}10^{r}a_{r}\equiv \sum _{r=0}^{k-1}10^{r}a_{r}{\pmod {2^{k}}}$ 
 $\sum _{r=0}^{n}10^{r}a_{r}\equiv \sum _{r=0}^{k-1}10^{r}a_{r}{\pmod {5^{k}}}$ 
 $\sum _{r=0}^{n}10^{r}a_{r}\equiv \sum _{r=0}^{k-1}10^{r}a_{r}{\pmod {10^{k}}}$ 

甚至非十進位下也是一樣。例如十二進位：2、3、4、6 都是 12 的因數，故某數的末 k 位除以 $2^{k}$ 、 $3^{k}$ 、 $4^{k}$ 、 $6^{k}$ ，所得餘數與原數同餘。

## 可由各數位判別

$$
\sum _{r=0}^{n}10^{r}a_{r}\equiv \sum _{r=0}^{n}a_{r}{\pmod {3}}
$$

$$
\sum _{r=0}^{n}10^{r}a_{r}\equiv \sum _{r=0}^{n}a_{r}{\pmod {9}}
$$

* ±3：所有位數加起來為 3 的倍數，即是。如 69255：（6＋9＋2＋5＋5）/3＝27/3＝9
* ±9：所有位數加起來為 9 的倍數，即是。如 69255：（6＋9＋2＋5＋5）/9＝27/9＝3

注意到我們現在是在十進位運算，而 9＝10－1。對於任意 $p$ 進位的非負整數除法，當除數是 $p-1$ 時被除數中所有數字相加的和仍與該被除數同餘。 
證明：

1. 如被除數為零，命題是平凡。
2. 在任何 $p$ 進位，首先考慮僅有最高位數字非零、其餘位均是零的正數，該數可寫成 $dp^{i}$ ，其中 $d$ 是最高位（第 $i$ 位）數字、 $1\leq d\leq p-1$ ，而 $p^{i}$ 表示後面有 $i$ 個零。（ $p$ 進位逢 $p$ 進一， $p$ 的 $i$ 次方自然是 1 後面 $i$ 個零。）
3. 那麼 $dp^{i}=dp^{i-1}p$ ，除以 $p-1$ 得 ${\frac {dp^{i-1}p}{p-1}}={\frac {dp^{i-1}(p-1)+dp^{i-1}}{p-1}}$ ，前項顯然整除，故 $dp^{i}=dp^{i-1}(p-1)+dp^{i-1}\equiv dp^{i-1}{\pmod {p-1}}$ ，推論得 $dp^{i}\equiv dp^{0}=d{\pmod {p-1}}$ 。
4. 而任何 $p$ 進位正整數均可寫成 $\sum _{i=0}^{n}d_{i}p^{i}$ 的形式，根據上面的結果，這個和（即是該數本身）顯然與所有數字之和 $\sum _{i=0}^{n}d_{i}$ 同餘。證畢。

$$
\sum _{r=0}^{n}10^{r}a_{r}\equiv \sum _{r=0}^{n}(-1)^{r}a_{r}{\pmod {11}}
$$

* ±11：將其奇數位之和及偶數位之和相減，如果是 0、11 等 11 的倍數，即是。如 19866→1＋8＋6－（9＋6）＝0
* ±7，±13：設正整數 $a=\sum _{r=0}^{n}1000^{r}a_{r}$ ， $1001=7\times 11\times 13$ ，所以

　
: $a\equiv \sum _{r=0}^{n}(-1)^{r}a_{r}{\pmod {7}},a\equiv \sum _{r=0}^{n}(-1)^{r}a_{r}{\pmod {13}}$

若 a＝75312289，則 a=75×1000²＋312×1000＋289，289－312＋75＝52，a 能被 13 整除，不能被 7 整除。

## 合數判別

若某整數能整除某合數則某整數必同時整除所有某合數的質因數。

* ±6：同時符合 ±2（末位是 0、2、4、6、8）和 ±3（相加可除盡）的條件（6＝2×3），如 66、7986252、99999996
* ±12：同時符合 ±4 和 ±3（相加可除盡）的條件（12＝ $2^{2}$ ×3），如 60

## 連續割頭法

$$
\sum _{r=0}^{n}10^{r}a_{r}\equiv a_{0}+10\sum _{r=1}^{n}10^{r-1}a_{r}{\pmod {k}}
$$

* ±7：將個位前的數字乘以 3 再與個位數相加，得出 7 的倍數即 7 的倍數。如 154→49→21→7
* ±13：將個位前的數字乘以 3 再與個位數相減，得出 13 的倍數即 13 的倍數。如 156→39→0

$$
\sum _{r=0}^{n}10^{r}a_{r}\equiv a_{0}+10a_{1}+100\sum _{r=2}^{n}10^{r-2}a_{r}{\pmod {k}}
$$

* ±23：將十位前的數字乘以 15 再與末兩位數相減，得出 23 的倍數即 23 的倍數。如 207→23
* ±31：將十位前的數字乘以 7 再與末兩位數相加，得出 31 的倍數即 31 的倍數。如 155→62
* ±37：將十位前的數字乘以 11 再與末兩位數相減，得出 37 的倍數即 37 的倍數。如 333→0

## 連續割尾法

若 $\sum _{r=0}^{n}10^{r}a_{r}\equiv 0{\pmod {k}}$ ，且 $10x\equiv 1{\pmod {k}}$

則 $a_{0}+10\sum _{r=1}^{n}10^{r-1}a_{r}\equiv xa_{0}+\sum _{r=1}^{n}10^{r-1}a_{r}\equiv 0{\pmod {k}}$

* ±7：將個位數乘以 2 再與個位前的數字相減，得出 7 的倍數即 7 的倍數。如 154→7
* ±19：將個位數乘以 2 再與個位前的數字相加，得出 19 的倍數即 19 的倍數。如 152→19

## 2 到 31 的整除規則總表

## 參見

* 除法、短除法
* 因數
* 同餘

## 參考資料