整除性检验
对于某一个正整数n来说,所谓整除性检验,指的是用来确定n是不是给定整数m的因数的一种方法,或者说,是用来辨明当m除以n时所剩下的余数是否为0的一种方法.如果回答为是,我们就说m能被n整除,或者说n是m的因数,还有第三种说法,即m是n的倍数.例如,m=36能被n=6整除,而m=56则不能,因为它除以6时剩下余数2.我们通过把除法完全作出,总能回答整除性问题,所以要使这检验有价值,必须一般地使所需工作比全部做完除法运算简单得多.
1和10,2和5
我们的数系的基是10.作出这个选择可能是个错误,不过现在要走回头路实在太晚了.无论你用什么数作基,都可以为那些是这基的因数的数提供很简单的整除性检验.10的因数是相互因数对(1,10)和(2,5).如果我们用基12,我们就有一个以1,2,3,4,6和12为因数的基.古代巴比伦人有30时用基60,这是一个很圆满的数,它的因数比12更多.然而以此为基的寻常算术要求学会乘法表直到60*60,我们中的大多数人不会愿意去学它.
如果我们用基b,而n这个数是b的因数,即b=kn,那么n的倍数的最后一位数就将遵循如下的模式:n,2n,3n,…,(k-1)n,0,因为kn=b用基b将写成10.于是当我们用基b经过n的所有倍数时,最后一位数字的模式就不定地重复自己.所以用基b时,当且仅当一个数的最后一位数是n,2n,…,0中之一,这数能被n整除.这就是说,只要检查最后一位数被n的整除性就够了,其他可以不管.
把这应用于我们的基10世界,我们知道,当且仅当一个数的最后一位数是2,4,6,8和0中之一,这数能被2整除.这就是说,当且仅当一个数的个位数是偶数,这数是偶数.同样地,当且仅当一个数的末位数是5或0,这数能被5整除.把这想法用于因数对(1,10),我们知道当且仅当一个数末位是0,这数能被10整除.我也许不该提到被1整除的整除性,因为当然每个数都有1这个因数,可是为了指出这个一般论述在这情形中也适用,我们注意到当且仅当一个数的末位数是1,2,3,…,9,0中之一,这数能被1整除;当然每个数都通过这一整除性检验!
这里十二进制或基12制的优点是显然的.以此为基,我们只要检查末位数就可以确定一个给定数能否被潜在因数1,2,3,4,6,12中任一个整除.例如,用基12,198这个数是14612=1*122+4*12+6,因为末位数能被3整除,所以这数显然能被3整除.用基10时,就不是这样明显(但是请注意后面对3的整除性检验).然而,究竟一个数是不是5或10的倍数,当它以十二进制表示时,就较不容易看出:例如用基12,我们将把十五写成1312(=1*12+3),这时因数5虽然依旧存在,却隐匿不见了.
4,8和16
从这里开始,检验略欠明显.当且仅当一个数的最后两位数字代表一个能被4整除的数,此数能被4整除.例如,根据4是16的因数这一事实,可知80776216是4的倍数,而121366则不是4的倍数,因为66除以4得余数2.唯一重要的是最后两位数字所代表的数,因为如果我们把它从原数中拿掉,我们就得到一个100的倍数,它当然是4的倍数.所以我们只需确定这最后两位数字是否也代表一个4的倍数.
注意这一过程满足我们为整除性检验所定的准则,因为它把包含一个具有任意位数字的给定数的问题变成了包含一个具有固定位数字的数的除法问题,在这个检验中,固定位数就是两位数字.
要确定被8整除的整除性,检验大致相同,只是我们必须检验的是末尾三位数字.就是说,当一个数的末尾三位数字所代表的数是8的倍数时,这数一定能被8整除.例如,你可以证明a=1894207376能被8整除,而b=3968844588则不能.这检验的基本原理与就4所作检验一样:我们只需检查从最后三位数字所得那部分数的行为,因为其余部分作为1000的倍数,肯定是8的倍数.
注意在8的情形中,我们不是只检验最后两位数字就行.事实上这样的假检验对上述a和b两个数都将给出假结果:8虽然不是76的因数,但它是a的因数,同时8是b的末尾两位数88的因数,但它不是b的因数.
你大概已经注意到对2,4和8所作的整除性检验之间的一般相似性.对于2=21,我们检查最后一位数字,对于4=22,我们检查最后两位数字,对于23=8,有关系的是最后三位数字组成的数.把这论述扩展下去,这模式就继续下去并能得到证实:当一个数的最后四位数字所形成的数能被24=16整除时,这个数能被16整除.更一般地,如果截取一个数的最后n位数字所得数能被2的幂2n整除,那么这个数能被2n整除.同样的观察也适用于5的幂:当一个数的最后n位数字所代表的数能被5的给定幂5n整除时,这个数能被5n整除.例如,52=25的倍数是易于确定的,因为它们正好是以25,50,75或00为末尾的数.
32对因数16作检验的一个例子是a=5210224.这确实是一个特别容易的检验,因为最后四位数字是0224.因为224/4=56,而56也能被4整除,所以我们断定224,从而断定我们原来的数a,是4*4=16的倍数.
3,6,9,12和15
对3所作整除性检验实在是一个巧妙的小玩意.你可能猜不到,但这是真实的:当且仅当一个数的各位数字的和能被3整除时,这个数能被3整除.例如,792能被3整除,因为它的各位数字的和是18,而721不是3的倍数,因为它的各位数字的和是10.
这是一个甚至对于很大的数也真正容易应用的检验,因为虽然各位数字的和s也可能是一个很大的数,我们可以把这检验用于s本身.换句话说,就像在去九的应用中一样,我们可以继续不断地应用这一步骤,直至以代表答数的一个一位正数结束:如果这个数字是3,6或9,我们检验的数就是3的倍数,否则不是.例如我们检验a=3406499617758.这时各位数字的和是69,而6+9=15,1+5=6,所以a能被3整除.与去九技术一样,我们可以用心算法解决这问题,即当我们头脑中的数大于9时,我们就进行这样的计算过程;这样一来,我们脑中的数永远不会大于18.对上述数a进行这心算时,我们是一面从左至右读出这数,或许用我们的手指来跟踪我们在这数中的位置,一面采取下列心算步骤.在下列明晰的工作过程中,我们停下来整理手头的数并把它替换成一个一位数的地方写在括弧内.一旦这样做了,我们就继续把给定数的各位数字从左至右读出:
3+4=7;7+0=7;7+6=13,(1+3=4);4+4=8;8+9=17,(1+7=8);8+9=17,(1+7=8);8+6=14,(1+4=5);5+1=6;6+7=13,(1+3=4);4+7=11,(1+1=2);2+5=7;7+8=15,(1+5=6);
因此a是3的倍数.
因为6=2*3,所以当且仅当这数同时满足对2和3的整除性检验时,它能被6整除.就是说,只有当一个数的个位数是偶数,而且它的各位数字的和能被3整除时,这个数是6的倍数.例如我们上面的数a,因为是偶数,所以不仅能被3整除,而且6也是它的因数.同样地,因为12=4*3,所以当且仅当一个数的最后两位数字所代表的数能被4整除,而且它的各位数字的和是3的倍数时,这个数是12的倍数.关于477168和861774这两个数是否能被12整除的问题,你可以自行判断.是否能被15整除的问题也容易解决,因为当且仅当一个数的末尾是5或0并且这数通过能被3整除的检验时,它有15=5*3这个因数.
如此容易地获得的这些结果,显示出简单地观察到许多算术运算能通过因数分解的运用而分成简易阶段这一事实所产生的力量.特别地,如果你不喜欢做“长”乘法,它们往往可以通过因数的乘法来避免.如果你知道乘数的因数的心算乘法表,你就不必去用长乘法:例如当你将一个给定数a乘以84时,长乘法的内容就是求出
a*84=a*(80+4)=a*80+a*4=10a*8+a*4,
所以只要你知道8倍表和4倍表,运算就可进行.另外一种计算方法是求出a*12*7———如果你知道你的12(和7)倍表的话.如果你不相信自己关于12的记忆,你可以用三个小乘法来代替:a*3*4*7.无论如何,我们发现长乘法总是可以避免的,直到乘数有一个你不知道乘法表的素因数时为止.对大多数人来说,第一个这种素数是13.
最后,在我们的3的倍数表中有9,你可能会希望,当且仅当一个数的各位数字的和能被9整除时,此数能被9整除.关于这事的证明与去九判断的证明密切相关,这里作一简短解释.你仍可以通过例子来使自己相信,例如,a=59252085能被9整除(所以a能被5*9=45整除),而107664虽然是3的倍数,但是能被9整除的检验失败.关于是否能被18和36整除的检验,我现在留给读者去描述.
对3和对9所作的检验之所以能获得成功,是由于这一事实:任何数与34它的各位数字之和,是模3和模9相等的.特别地,一个数恰恰当它的各位数字之和除以3或9所得余数为0时,这个数除以3或9所得余数为0.这又是下述事实的结果:10的任何幂除以3或9时所得余数为1,因为由一连串9形成的数是3和9的倍数.*
这是供参加数学奥林匹克的童星们作热身练习用的一组曲折的小问题的基础.你有一个数a,你把它的各位数字任意置换,得另一个数b.证明d=a-b不可能是素数.
这看上去是可怕的:这个差d似乎可以是任何数,我们怎么能说出多少有关它的素因数的话来呢?我们中的很多人肯定不知道该从哪里起步,只能凝视着这问题,不存在解出的希望.然而一个成功的数学家在挑战面前必须保持爱玩的精神,让问题随意前行,哪怕所走的路看上去达不到所搜寻的目标.关于a和b这两个数,我们可以说一件事:它们的各位数字的和是恒等的,所以a和b除以9时所得余数相同.当我们将两数相减时,这余数便消失,所得数d是9的倍数.现在我们能看到回家的路了:因为d是9的倍数,它当然不是素数.
我们终于看到,关于素数的那一小段是转移注意力的话.如果需要我们解释为何d有因数9,这问题应该很容易,即使那是比所需结论更强的结论.从某种意义上讲,这问题所考验的是被考验者是否具有数学勇气暂时把这特殊的结论搁在一边,去追寻问题中的数学路标.得出的教训是:学生必须相信他们的训练而不要胆怯———说比做容易.
7,11和13
还有三个难对付的家伙:7,11和13.它们是不能整除10的素数,所以它们的倍数在用基10写出时不太容易辨认.十一离十很近,是最容易对付的.11的整除性规则虽然是迄今为止最复杂的,但用起来却很容易.
如果一个数n的各位数字依次加上交错的正负号后相加所得和能被11整除,那么n能被11整除,否则不能.
例如,用我们的规则检验
a=56518:8-1+5-6+5=11,
这是11的倍数,所以11是我们的数a的因数.这里我们是按照各位数字的值的上升次序求和,如果按相反次序,结果相同,但正负号相反.一个数的正负号不影响它的整除性,因此在这里并不重要.(注)
另一种等效的检验方法进行如下:设s是a的偶数位数字的和,t是其余数字的和.于是当且仅当11是s-t的因数时,11是a的因数.检验数s-t或者与第一种检验中的检验数相同,或者是它的负数,视问题中的数a具有偶数或奇数长度而定.在两种情形中,都得到相同的结论.当然,用任何一种检验方法,检验数都可以是负的.例如,如果我们取a=814396,两种方法中的检验数都是(1+3+6)-(8+4+9)=10-21=-11,又是11的倍数(你在任何时候都可以把负号略去).*
如同其他取各位数字之和的检验一样,我们可以重新把检查被11整除性的步骤用于所得各位数字之和,直至手头的数小到足以通过检验来对付.如果我们尽可能长久地继续下去,将发生两种情况之一.或者我们将终结于一个非零一位整数,这时这数不能被11整除,或者如果这数是11的倍数,我们将终结于0.例如,如果交错和等于154,将这检验用于154,得4-5+1=0.
这里有一个你可以做得非常容易的例子,它远远胜过用计算器的直接除法:
a=16193818284590452;
s=(6+9+8+8+8+5+0+5)-(1+1+3+1+2+4+9+4+2)=49-27=22;2-2=0,
所以a能被11整除.
所谓回文数,就是倒转仍相同的数,例如121,181,2002.我们容易检查出181不是11的倍数,但121和2002都是.事实上每一个具有偶数位数字的回文数都有11这个因数,它的原因我肯定你很快能使自己相信,就是偶数位置上数字和奇数位置上数字的和s和t必然相同,所以它们的差是0,证明这个数能被11整除.
最后,有一个用于7和13的以数的各位数字为基础的检验.事实上这检验也可用于11,但比上述用于这数的检验复杂得多.
设a是给定数.从右开始,取每三位数为一段,按被11整除性检验所用同样方式,求出交错和s.恰恰当s能被7或13整除时,a能被7或13整除.例如,a=24889375能被7整除,但不能被13整除.为明白这道理,我们计算检验和s:
s=375-889+024=-490=-70*7;
但490不能被13整除,这很快就被检查出来.当然,我们既已有了7和13的整除性检验,设计出这些数字的小倍数即14,21,28,…和26,39,52,…等的检验就是一件简单的事情,只要把这些检验和所含其他因数的检验结合起来就可以了.
我们用一个大数例子来作结束.a=98858760能否被8008整除?从除数的因数分解开始:8008是偶数长度回文数,所以有11这个因数,同时也显然有8这个因数:作除法得8008=11*8*91=11*8*7*13,所以我们只需检验a能否被这四个数整除.因为760/2=380,而380能被4整除(因为80能被4整除),所以a是8的倍数.利用交错和,我们可同时对7,11和13作检验:
s=760-858+098=0,
因为0当然是这三个数的倍数,我们断定8008确实是a的因数.
……
展开
