作者 | 邵品琮 张景中 于劭

来源 |《数学通报》，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=29取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及5的因子时(K，S是自然数)，我们可以把D是否能除尽N的问题化为能否除尽 N 及能否除尽N的问题了，而其中对形式的因子判别法是众所周知的。

[例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 改写)