主题
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" 的意思是“估计为毫无价值的行为或习惯”。)


另请参阅

同余, 数字和, 整除, 除数, 模数, 九的法则

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 中被引用

整除性检验

请引用为

Weisstein, Eric W. “整除性检验。” 来自 MathWorld——一个 Wolfram Web 资源。 https://mathworld.net.cn/DivisibilityTests.html

主题分类