正整數(shù)被素?cái)?shù)p整除的判別法

管訓(xùn)貴

(泰州學(xué)院 數(shù)理學(xué)院，江蘇 泰州 225300)

0 引言

判別一個(gè)正整數(shù)M能否被某素?cái)?shù)p整除這一問題，1963年華宏鳴[1]進(jìn)行了探討并證明了命題1和2。

命題1正整數(shù)M能被素?cái)?shù)p(p≠2,5)整除的充要條件是截去M的末位數(shù)后，在十位數(shù)上加上末位數(shù)的a倍，所得的數(shù)能被p整除，其中a滿足條件lp+1=10a。更一般地說，有正整數(shù)M=10x+y能被素?cái)?shù)p整除的充要條件是M′=x+ay能被p整除。

命題2正整數(shù)M能被素?cái)?shù)p(p≠2,5)整除的充要條件是截去M的末位數(shù)后，在十位數(shù)上減去末位數(shù)的a倍，所得的數(shù)能被p整除，其中a滿足條件lp-1=10a。更一般地說，有正整數(shù)M=10x+y能被素?cái)?shù)p整除的充要條件是M′=x-ay能被p整除。

后來，文獻(xiàn)[2-6]又相繼給出了其他判別法。本文給出一個(gè)比較簡(jiǎn)單的判別法，用以判別一個(gè)正整數(shù)M能否被某素?cái)?shù)p整除?？紤]到一個(gè)正整數(shù)被2和5整除與否，僅需看末位數(shù)即可，故不妨設(shè)p≠2,5。

由定理1直接可得推論1、推論2和推論3。

1 定理1及推論的證明

不妨設(shè)k>0。先用數(shù)學(xué)歸納法證明knMn≡bn(modp)。

當(dāng)k=1時(shí)，kM1=k(a0+10a1)=(kc0+a1)+(10k-1)a1≡b1(modp)，結(jié)論成立。假設(shè)k=l時(shí)，結(jié)論成立，即klMl≡bl(modp)，則當(dāng)k=l+1時(shí)kl+1Ml+1=kl+1(Ml+10l+1al+1)=k·klMl+(10k)l+1al+1≡k·bl+(10k)l+1al+1≡k·bl+al+1+((10k)l+1-1)al+1≡k·cl+al+1+((10k)l+1-1)al+1≡bl+1(modp)，這說明結(jié)論對(duì)k=l+1也成立。因此knMn≡bn(modp)。由此知p|(knMn-bn)。因?yàn)間cd(kn,p)=1，所以p|Mn?p|bn。定理1得證。

另外，當(dāng)k=2時(shí)，10×2≡1(mod 19)，故由定理1知，對(duì)?i=0,1,…,n-1,若bi+1=2ci+ai+1，bi+1≡ci+1(mod 19)，其中c0=a0，|ci+1|≤9，則19|Mn?19|bn。推論1得證。

當(dāng)k=7時(shí)，10×7≡1(mod 23)，故由定理1知，對(duì)?i=0,1,…,n-1,若bi+1=7ci+ai+1，bi+1≡ci+1(mod 23)，其中c0=a0，|ci+1|≤11,則23|Mn?23|bn。推論2得證。

當(dāng)k=-3時(shí)，10×(-3)≡1(mod 31)，故由定理1知，對(duì)?i=0,1,…,n-1,若bi+1=-3ci+ai+1，bi+1≡ci+1(mod 31)，其中c0=a0，|ci+1|≤15,則31|Mn?31|bn。推論3得證。

2 應(yīng)用舉例

例1試證：1)19|9 739 153；2) 31|/19 631 126。

證明1)易知，2×3+5=11，11≡11(mod 19)，2×11+1=23，23≡4(mod 19)，2×4+9=17，17≡17(mod 19)，2×17+3=37，37≡-1(mod 19),2×(-1)+7=5,5≡5(mod 19),2×5+9=19,19|19，所以19|9 739 153。

2) 易知，-3×6+2=-16，-16≡15(mod 31)，-3×15+1=-44，-44≡-13(mod 31)，-3×(-13)+1=40，40≡9(mod 31)，-3×9+3=-24，-24≡7(mod 31)，-3×7+6=-15，-15≡-15(mod 31)，-3×(-15)+9=54，54≡-8(mod 31)，-3×(-8)+1=25，31|/25，所以31|/19 631 126。

例2判別5 870 699能否被23整除。

解易知，7×9+9=72，72≡3(mod 23)，7×3+6=27，27≡4(mod 23)， 7×4+0=28，28≡5(mod 23)，7×5+7=42，42≡-4(mod 23)，7×(-4)+8=-20，-20≡3(mod 23)，7×3+5=26，23|/26，所以5 870 699不能被23整除。

說明如果在定理中取k=1,-2,-1,4,-5,3,-11,-4,13,-14,16,6,-6,-20,-7,22,8,25,9,-29，還可以得到被素?cái)?shù)p=3,7,11,13,17,29,37,41,43,47,53,59,61,67，71,73,79,83,89,97整除的判別法(以上得到了100以內(nèi)除2，5以外的全部素?cái)?shù)的整除性判別法)。由于gcd(10,p)=1，即同余方程10k≡1(modp)總是有解的，故本定理涵蓋了被任意素?cái)?shù)p整除的判別法。