主題
Search

整除性檢驗


一般來說,整數 n 可以被 d 整除 當且僅當 數字和 s_(d+1)(n) 可以被 d 整除。

將正十進位制整數 a 逐位寫成 a_n...a_3a_2a_1a_0 的形式。 以下規則透過檢查其數字的 同餘 性質來確定 a 是否可以被另一個數 整除。 在 同餘 符號中,n=k (mod m) 表示當 n 除以模數 m 時,餘數為 k。(請注意,對於任何基數,10^0=1=1 始終成立。)

1. 所有整數都可以被 1 整除

2. 10^1=0 (mod 2),因此對於 n>=110^n=0 (mod 2)。 因此,如果最後一位數字 a_0 可以被 2 整除(即為偶數),那麼 a 也可以被 2 整除。

3. 10^0=1, 10^1=1, 10^2=1, ..., 10^n=1 (mod 3)。 因此,如果數字和 s_(10)(n)=sum_(i=0)^(n)a_i 可以被 3 整除,那麼 a 也可以被 3 整除 (Wells 1986, p. 48)。 一般來說,如果 n 的數字的任何排列的順序之和可以被 3 整除,那麼 n 也可以被 3 整除。

4a. 10^1=2, 10^2=0, ..., 10^n=0 (mod 4)。 因此,如果最後兩位數字可以被 4 整除,那麼 a 也可以被 4 整除。

4b. 如果 r=a_0+2a_1 可以被 4 整除,那麼 a 也可以被 4 整除。

5. 10^1=0 (mod 5),因此對於 n>=110^n=0 (mod 5)。 因此,如果最後一位數字 a_0 可以被 5 整除(即為 5 或 0),那麼 a 也可以被 5 整除。

6a. 如果 a 可以被 3 整除 且為偶數,那麼 a 也可以被 6 整除

6b. 10^1=-2, 10^2=-2, ..., 10^n=-2 (mod 6)。 因此,如果 r=a_0-2sum_(i=1)^(n)a_i 可以被 6 整除,那麼 a 也可以被 6 整除。 當然,可以使用相同的步驟進一步簡化最終的數字。

7a. 10^1=3, 10^2=2, 10^3=-1, 10^4=-3, 10^5=-2, 10^6=1 (mod 7),然後序列重複。 因此,如果 r=(a_0+3a_1+2a_2-a_3-3a_4-2a_5)+(a_6+3a_7+...)+... 可以被 7 整除,那麼 a 也可以被 7 整除。 這種方法是帕斯卡發現的。

7b. 另一種檢驗方法是先將 a_n 乘以 3,然後加到 a_(n-1),然後重複此過程,直到 a_0。 當然,可以使用相同的步驟進一步簡化最終的數字。 如果結果可以被 7 整除,那麼原始數字也可以被 7 整除 (Wells 1986, p. 70)。

7c. 第三種檢驗方法是將 a_0 乘以 5,然後將其加到 a_1,依此類推,直到 a_n。 當然,可以使用相同的步驟進一步簡化最終的數字。 如果結果可以被 7 整除,那麼原始數字也可以被 7 整除 (Wells 1986, p. 70)。

7d. 給定一個數字,形成兩個數字 xy,使得 x 由該數字的所有數字組成,但不包括最後一位(個位)數字,而 y 是最後一位數字。 計算 x-2y 並重復此過程。 那麼,當且僅當最後一步的數字可以被 7 整除時,原始數字可以被 7 整除。

8. 10^1=2, 10^2=4, 10^3=0, ..., 10^n=0 (mod 8)。 因此,如果最後三位數字可以被 8 整除,更具體地說,如果 r=a_0+2a_1+4a_2 可以被 8 整除,那麼 a 也可以被 8 整除 (Wells 1986, p. 72)。

9. (九的法則)。 10^0=1, 10^1=1, 10^2=1, ..., 10^n=1 (mod 9)。 因此,如果數字和 s_(10)(n)=sum_(i=0)^(n)a_i 可以被 9 整除,那麼 a 也可以被 9 整除 (Wells 1986, p. 74)。

10. 10^1=0 (mod 10),因此如果最後一位數字是 0,那麼 a 可以被 10 整除

11. 10^1=-1, 10^2=1, 10^3=-1, 10^4=1, ... (mod 11)。 因此,如果 r=a_0-a_1+a_2-a_3+... 可以被 11 整除,那麼 a 也可以被 11 整除。

12. 10^1=-2, 10^2=4, 10^3=4, ... (mod 12)。 因此,如果 r=a_0-2a_1+4(a_2+a_3+...) 可以被 12 整除,那麼 a 也可以被 12 整除。 也可以透過檢查 a 是否可以被 3 和 4 整除來檢驗是否能被 12 整除。

13. 10^1=-3, 10^2=-4, 10^3=-1, 10^4=3, 10^5=4, 10^6=1 (mod 13),並且模式重複。 因此,如果 r=(a_0-3a_1-4a_2-a_3+3a_4+4a_5)+(a_6-3a_7+...)+... 可以被 13 整除,那麼 a 也可以被 13 整除。

有關 13 的其他檢驗方法,請參見 Gardner (1991)。

一個有趣的英語語言小知識是,單詞 "indivisibilities" 比任何其他常用詞都含有更多的 "i"(實際上是七個)。 (其他包含七個 i 的單詞包括 honorificabilitudinitatibus、indistinguishabilities、indivisibilities 和 supercalifragilisticexpialidocious。 包含八個 i 的短語包括 "Illinois fighting Illini" 和 "infinite divisibility"。 包含最多 i 的英語單詞是 floccinaucinihilipilification(九個 i),其中 "floccinaucinihilipilification" 的意思是“估計為毫無價值的行為或習慣”。)


另請參閱

同餘, 數字和, 整除, 除數, 模數, 九的法則

使用 探索

參考文獻

Burton, D. M. "特殊整除性檢驗。" §4.3 in Elementary Number Theory, 4th ed. Boston, MA: Allyn and Bacon, pp. 89-96, 1989.Dickson, L. E. History of the Theory of Numbers, Vol. 1: Divisibility and Primality. New York: Dover, pp. 337-346, 2005.Gardner, M. "整除性檢驗。" Ch. 14 in The Unexpected Hanging and Other Mathematical Diversions. Chicago, IL: Chicago University Press, pp. 160-169, 1991.Wells, D. The Penguin Dictionary of Curious and Interesting Numbers. Middlesex, England: Penguin Books, p. 48, 1986.

在 中被引用

整除性檢驗

請引用為

Weisstein, Eric W. “整除性檢驗。” 來自 ——一個 資源。 https://mathworld.tw/DivisibilityTests.html

主題分類