介绍一种简单的因子判别法

luyuanhong

介绍一种简单的因子判别法

作者 | 邵品琮 张景中 于劭

来源 |《数学通报》，1956（05）

当我们想知道一个整数能不能除尽另一个整数时，一般地，除了是用 2，3，5，…… 这些极个别的数去除别的数之外，总得老老实实去除一除。这件工作是很麻烦的。这里介绍一种方法，利用它能判别一个数能不能除尽另一个数，在我们只需要知道一个数能不能除尽另一数而不用知道它们的商时，这个方法是很适用的。

为了说着方便，当然可以假定除数 D 和被除数 N 都是正的。我们知道，被除数 N 越小，除起来就越省力；要是我们对于 D 和 N 能找到一个比 N 小的 R ，使得 D|R 是 D|N 的充分必要条件，那问题不是就简单了吗？这里介绍的方法的基本意思，就是给出一个规律，使我们对任意的正整数 D ，N ，都能找到一个比 N 小的 R ，满足：

D|R ＜=＞ D|N ( D|R 就是 D 能除尽 R 的意思)。

这个规律要是把它叙述成定理的形式，就是这样的：

“D ，N 都是正整数；N = 10a+b( 10＞b ，a,b 都是正整数)则我们一定能找到一个只和 D 有关的整数 T ，使 D|R = a+Tb ＜=＞ D|N ”

(以后把 T 叫做 D 的“判别数”)。

这里先看一个例子；证明放在后面。

[例 1] 29 能不能除尽 899 ?

对 29 取判别数 T=3 。

899 = 10×89+9 ，故 a=89 ，b=9 。

故：R = a+Tb = 89+27 = 116 。

29 能除尽 116 吗？我们可以再化简一次：

116 = 10×11+6 ，故 a=11，b=6 ，

因而 R = a+Tb = 11+18 = 29 。

29 是能除尽 29 的；从而就能除尽 116 ，也就能除尽 899 。验算一下，就知道上述结论是对的。

我们要说明一下：对 D=29 取判别数 T=3 是对任意被除数 N 都成立的，这也放在后面证明。

下面证明，对任一除数 D ，总可以找到判别数 T ，而且具体地把它找出来：

(1)在 D 可以表成 10n+1 的情形下(n 正整数)，我们取 T = -n ，则对任意被除数 N = 10a+b ，有 D|R = a+Tb ＜=＞ D|N 。

证明：

R = a-nb = a-n(N-10a) = a+10na-nN = a(10n+1)-nN = aD-nN 。

因为 D = 10n+1 ，所以 D 和 n 互素；上面的等式指出：D 能除尽 R 时 D 就能除尽 nN ，因而就能除尽 N 。反之，若 D 能除尽 N ，等式就直接指出：D 能除尽 R。

(2)当 D 可表为 10n+3 时(n 正整数)，取 T = 3n+1 ，则对任意的被除数 N = 10a+b ，有 D|R = a+Tb ＜=＞ D|N 。

证明：

R = a+(3n+1)b = a+(3n+1)(N-10a) = N(3n+1)-30na-9a = N(3n+1)-3a(10n+3) = N(3n+1)-3aD 。

上面的等式指出：若 D 能除尽 R ，则 D 能除尽 N(3n+1) 。但是因为 D = 10n+3 = 3(3n+1)+n ，而 n 和 3n+1 互素，故 D 和 3n+1 也互素，所以，D 就能除尽 N 了。若 D 能除尽 N ，则等式直接说明，D 是能除尽 R 的。

一般说来，我们很容易证明下表所列之规律：

设被除数 N = 10a+b ，有：



从上表可以看出，例 1 中对 D=9 取 T=3 是正确的。

[例2] 41 是否能除尽 3731 ？

41 = 4×10+1 ，n=4 。41 是 10n+1 形式。

因而取 T = -n = -4 ，

R = 373+1×(-4) = 369 。

对 369 再用上述运算：

R = 36+(-4)×9 = 0 ，

所以，41 能除尽 3731 。

下面我们采用一种比较简单的写法，如：



故：41 | 3731 。

当 D 中有形式为 2^k×5^s 的因子，而 D/(2^k×5^s) 不再包含 2 及 5 的因子时( k,s 是自然数)，我们可以把 D 是否能除尽 N 的问题化为 2^k×5^s 能否除尽 N 及  D/(2^k×5^s) 能否除尽 N 的问题了，而其中对 2^k×5^s 形式的因子判别法是众所周知的。

[例3] 问 95 能否除尽 3735 ？

95=19×5 ，显然 5|3735 。我们考虑 19 能否除尽 3735 ：



因 19 除不尽 44 ，所以 19 除不尽 3735 ，结果得出结论：

95 不能除尽 3735 。

(本文系根据 Edwin Brenman, Testing for Divisibility, Scripta Mathernatica 1955 Vol. XXI,No.1，p.88-90 改写)

luyuanhong

下面是我过去在《数学中国》发表过的几个帖子，可供参考：

luyuanhong

luyuanhong

luyuanhong

luyuanhong