整除性檢驗(yàn)法（續(xù)）

何鴻猷

【摘要】設(shè)p為除2，5以外的所有質(zhì)數(shù)和不含因數(shù)2、5的所有合數(shù).設(shè)n為循環(huán)節(jié)位數(shù).①A為任意整數(shù)，從A的低位向高位n位n位分節(jié)，各節(jié)之和與A對(duì)p同余.②當(dāng)p為質(zhì)數(shù)，n為偶數(shù)，A為n位數(shù)時(shí)，奇一半減去偶一半的差與A對(duì)p同余.③循環(huán)小數(shù)是無限循環(huán)的，當(dāng)p為質(zhì)數(shù)，n為偶數(shù)時(shí)，凡與所有奇數(shù)節(jié)自由循環(huán)節(jié)位數(shù)相等的左右各半數(shù)碼完全相同的數(shù)，均能被該質(zhì)數(shù)整除.④任一整數(shù)A若能被n位全9數(shù)整除，它也能被循環(huán)節(jié)位數(shù)等于n位的所有數(shù)整除.⑤加數(shù)的同余數(shù)之和與和數(shù)對(duì)p同余.

【關(guān)鍵詞】全9數(shù)；同余；自由循環(huán)節(jié)

1[]7=0.1·42857·，循環(huán)節(jié)是6位.999999÷7=142857；857+142=999；57+28+14=99；

7+5+8+2+4+1=27，7+2=9.再看142857÷333=429；142857÷111=1287；142857÷37=3861；142857÷27=5291.142857÷11=12987；142857÷33=4329；142857÷3=47619.這是為什么呢？都和循環(huán)節(jié)位數(shù)有關(guān)系.正契合整除性檢驗(yàn)法.

為敘述方便，我們將各位數(shù)碼都是9的數(shù)稱為n位全9數(shù)，以n位全9數(shù)為分母的真分?jǐn)?shù)化為小數(shù)為純循環(huán)小數(shù)，而且循環(huán)節(jié)位數(shù)是n位.1[]999=0.001001001…，n=3.1[]99=0.010101…，n=2.1[]9=0.1111…，n=1.能被n位全9數(shù)整除的n位數(shù)，也只能是n位全9數(shù).6位全9數(shù)中有小于6的全9數(shù)因數(shù)：1位、2位、3位.142857從低位向高位依n分節(jié)：3位3位分節(jié)各節(jié)之和是999；2位2位分節(jié)各節(jié)之和是99；1位1位分節(jié)各節(jié)之和是9.999，99，9自然分別能整除999999，說明142857不僅能被999整除；也能被99整除；還能被9整除.333，111，37，27的循環(huán)節(jié)位數(shù)都是3位；11，33的循環(huán)節(jié)位數(shù)都是2位；3的循環(huán)節(jié)位數(shù)是1位，所以142857分別也能被這些數(shù)整除.任一整數(shù)A，從低位向高位n位n位分節(jié)，各節(jié)之和如是n位全9數(shù)，則凡能被n位全9數(shù)整除的任意整數(shù)，它一定能被循環(huán)節(jié)是n位的所有數(shù)整除.

1[]9901=0.0·00100999899·.循環(huán)節(jié)位數(shù)是12位，9901能整除12全全9數(shù)，12位全9數(shù)中小于12位的全9數(shù)因數(shù)有：1位、2位、3位、4位、6位.12位全9數(shù)自然能被它的各位全9數(shù)因數(shù)整除.循環(huán)小數(shù)的有效數(shù)字是100999899，也能被1位、2位、3位、4位、6位等全9數(shù)整除.因此：無論質(zhì)數(shù)還是合數(shù)凡是循環(huán)節(jié)位數(shù)是1位、2位、3位、4位、6位的都能整除100999899.p為質(zhì)數(shù)或異因同循合數(shù)，n位循環(huán)小數(shù)的有效數(shù)字能被小于n位全9數(shù)的各全9數(shù)因數(shù)整除；也能被循環(huán)節(jié)位數(shù)分別等于它們的位數(shù)的所有數(shù)整除.

一、設(shè)p為除2，5以外的所有質(zhì)數(shù)以及不含因數(shù)2，5的所有合數(shù).以p為分母的真分?jǐn)?shù)化為小數(shù)為純循環(huán)小數(shù)，再設(shè)循環(huán)節(jié)位數(shù)為n位，則p能整除n位全9數(shù).如p1為7，13，91，21，63，39，117，77，143，1001，231，693，429，1287…循環(huán)節(jié)位數(shù)n都是6位，都能整除6位全9數(shù).

欲判斷整數(shù)A能否被p 整除，從A的低位向高位n位n位分節(jié)，各節(jié)之和若能被p整除，A就能被p 整除.要問是什么道理？用一句話回答：就是各節(jié)之和與A對(duì)p同余.同余是數(shù)學(xué)的一個(gè)分支，屬于數(shù)論范疇，還有個(gè)專用符號(hào)，如23≡16（mod 7），意即23和16對(duì)7同余.若各節(jié)之和等于H，如何證明A≡H（mod p）呢？回答這個(gè)問題，要從：

（1）n位全9數(shù)能被p 整除.

（2）n的倍數(shù)nb位全9數(shù)能被p整除.

（3）b個(gè)n位全9數(shù)之和能被p整除.

（4）nb位全9數(shù)加1等于A，則A≡1（mod p）.

（5）設(shè)C為任一整數(shù)，C·A=R，R-C=D，D能被p 整除.根據(jù)中國(guó)余數(shù)定理：因數(shù)的余數(shù)積等于積的余數(shù)，所以C≡C（mod p），A≡1（mod p），C·1=C，R≡C（mod p）或根據(jù)同余數(shù)的定義：C，R二整數(shù)的差若能被p整除，則R≡C（mod p），

（6）A= 4523.896315.470563各節(jié)之和與A是否對(duì)p同余？

4723000000000000+896315000000+470563=4523896315470563=A.

4723000000000000≡4723（mod p1），896315000000≡896315（mod p1），470563≡470563（mod p1）

4723+896315+470563=1371601=H，各加數(shù)的同余數(shù)之和，恰是A從低位向高位n位n位分節(jié)的各節(jié)之和數(shù).根據(jù)中國(guó)余數(shù)定理：加數(shù)的余數(shù)和等于和的余數(shù). 引論：加數(shù)的同余數(shù)之和與和數(shù)同余. A≡H（mod p1），所以A≡H（mod p）.

二、為什么當(dāng)n為偶數(shù)時(shí)，p為質(zhì)數(shù)或p為合數(shù)但合數(shù)的各質(zhì)因數(shù)的循環(huán)節(jié)位數(shù)都是偶位.且相互是奇倍數(shù)時(shí)，判斷整數(shù)A能否被p整除，可以從A的低位向高位按二分之n位分節(jié)，然后奇二分之n位與奇二分之n 位相加，偶二分之n位與偶二分之n位相加，二和相減，差若能被p整除，A就能被p整除呢？用一句話回答就是二和之差和A對(duì)p必須同余0.方能被p整除，否則不能.

999999÷7=142857，142857÷999=143.

999999÷999=10011001÷7=143.

1001×495=495495，495495÷7=70785，143×495=70785.

1001擴(kuò)大任一3位數(shù)倍，就成了一個(gè)前后3位數(shù)碼完全相同的數(shù)，凡這樣的數(shù)能被循環(huán)節(jié)位數(shù)是6的質(zhì)數(shù)整除.同樣n為偶數(shù)時(shí)，前二分之n位與后二分之n位數(shù)碼完全相同的數(shù)、能被質(zhì)數(shù)p整除.

nb位全9數(shù)，當(dāng)n為偶位、b為奇數(shù)時(shí)，nb位全9數(shù)除以p的商對(duì)折起來是二分之nb位全9數(shù).也可以作如下理解：循環(huán)小數(shù)是無限循環(huán)的，循環(huán)節(jié)位數(shù)是指短循環(huán)節(jié)位數(shù)而言，是唯一的，自由循環(huán)節(jié)就有無窮多，兩節(jié)兩節(jié)循環(huán)，三節(jié)三節(jié)循環(huán)……十節(jié)十節(jié)循環(huán)都可以看成是自由循環(huán)節(jié)，但只有節(jié)數(shù)是奇倍數(shù)時(shí)對(duì)折起來各位才能都是9.只要與

奇數(shù)節(jié)位數(shù)相等的左右二分之一數(shù)碼完全相同的數(shù)都能被該質(zhì)數(shù)整除.合數(shù)：（1）當(dāng)各質(zhì)因數(shù)的循環(huán)節(jié)位數(shù)都是偶位時(shí).（2）循環(huán)節(jié)或自由循環(huán)節(jié)位數(shù)都相等時(shí).（3）對(duì)折起來各位又能都是9時(shí).所以自由循環(huán)節(jié)必須是奇數(shù)節(jié).這樣，左右二分之n位數(shù)碼完全相同的數(shù)，也才能為各因數(shù)所整除.才能為本合數(shù)所整除.

999999÷11=090909，909+090=999，90909÷999=91.495495÷11=045045.

11×7=77；11×13=143；7×13=91；7×13×11=1001，所以：

258258÷77=3354，258258÷143=1806，258258÷91=2838，258258÷11=23478，258258÷1001=258，因此，設(shè)p2為7，13，91，77，143，1001.

987654-123123=864531，987654≡864531（mod p2）

987654-987987= 654-987=-333，987654-654654=333000.987-654=333，

987654≡-333（mod p2），987654≡333000（mod p2）987654與333對(duì)p2不同余.（因與同余數(shù)符號(hào)相反）如果僅判斷能否整除，無論偶位減奇位，或奇位減偶位只要差與p同余0，就判斷能整除，否則不能整除.

上面（一）（6）中各加數(shù)的同余數(shù)還可以再求出位數(shù)更少的同余數(shù)，即：4723+896315+470563=1371601.4723-004004=723-4=719；4723≡719（mod p2），896315-896896=315-896=-581；896315≡-581（mod p2）；470563-470470=563-470=93.470563≡93（mod p2）719+（-581）+93=231.1371601≡231（mod p2），（加數(shù)的同余數(shù)之和與和數(shù)對(duì)p同余）723-4+315-896+563-470=（723+315+563）-（4+896+470），比較就可以明白，恰是從A的低位向高位3位3位分節(jié)：723，351，563是奇3位.004，896，470是偶3位.這是從普遍適用的方法中推導(dǎo)出來的一個(gè)方法.

（723+315+563）-（4+896+470）=1601-1370=231，1371601≡231（mod p2），4723896315470563≡231（mod p2）.

三、設(shè)Q為質(zhì)數(shù)2，5及僅含因數(shù)2，5的合數(shù).1[]Q化為小數(shù)為有限小數(shù)，設(shè)有限小數(shù)的位數(shù)為h.設(shè)想1后面有若干位0.，Q除至幾位0正好除盡，h就是多少位，所以，任一整數(shù)后面只要有h位0，該數(shù)就能被Q整除.所以任一整數(shù)A與末h位數(shù)對(duì)Q同余.因此判斷整數(shù)A能否被Q整除，只要末h位能被Q整除A就能被Q整除.

四、設(shè)P·Q為含有因數(shù)2，5的合數(shù)，1[]p·Q化為小數(shù)為混循環(huán)小數(shù).如p·Q=88，1[]88=0.0113·6·.3位不循環(huán)，兩位循環(huán).即h=3，n=2.A=2268948528.判斷A能否被88整除？28+85+94+68+22=297.97+2=99.A≡99（mod p）.A≡528（modQ）根據(jù)中國(guó)余數(shù)定理：因數(shù)的余數(shù)積等于積的余數(shù).引論：因數(shù)的同余數(shù)之積與積（A）對(duì)p·Q同余，即：99×528=52272，A≡52272（mod 88）.52272÷88=594.答：A能被88整除.