數(shù)的整除性判斷的通用公式

如何判斷一個大整數(shù)N能被某個特定的質(zhì)數(shù)p整除，

XES老師讓大家直接背以下結(jié)論：

判斷能被2、5整除，看個位；判斷能否被3、9整除，看各數(shù)位和能否被3、9整除； 等等。

我們嘗試用逐步逼近的推理給出一個判斷此類問題的通用辦法。比如判斷11026能否被37整除，我們也能很快得到答案。理解以下推理，我們對同余方程的用到的定理也有更深的了解。

1、? 判斷能被10整除，直接看個位。12345被10除，余數(shù)是5。顯然12345=1*10000+2*1000+3*100+4*10+5，十位以上都能被10整除，僅僅看個位即可。

2、? 由1我們推出，判斷2和5整除與否，直接看個位就好了。

3、? 由1和2，我們推出，判斷N能否被2的m次方或5的m次方整除，直接看末m位就好了。

由1-3，實際上我們已經(jīng)完成了所有偶數(shù)質(zhì)數(shù)（以及5）的整除性判斷。以下我們就可以關(guān)注奇素數(shù)（除5以外）的整除判定方法。

4、? 對9的判斷。12345=(1*9999+1)+(2*999+2)+(3*99+3)+（4*9+4）+5，因此判定12345能否被9整除，只要判定（1+2+3+4+5）能否被9整除。

5、? 對11的判斷。12345=1*10000+2*1000+3*100+4*10+5

=（1*9999+1）+（2*1001-2）+(3*99+3)+(4*11-4)+5

=1*9999+2*1001+3*99+4*11+(1-2+3-4+5)

我們只需要判斷后面括號中1-2+3-4+5除以11的余數(shù)就好了。

以上是對10附近兩個奇數(shù)整除性判斷的方法? 。關(guān)鍵是利用10^m余數(shù)特點簡化計算。

6、? 由4和5兩條，我們發(fā)現(xiàn)判斷N能否被奇素數(shù)整除，關(guān)鍵是10^m-1能否被p整除。

7、? 由此我們探求的目標(biāo)就是求10^m模p余1的同余方程求解。

8、? 原根的概念。數(shù)論中費馬小定理和推廣的歐拉定理。

9、? 由此，我們可以歸納出任何質(zhì)數(shù)p的最優(yōu)化的整除判定方法。對于給定的N和p，我們先找到使得10^m-1能夠被p整除的m。我們就能將大整數(shù)截成m位的小整數(shù)進行同余計算。

回到我們的例子，如何判斷11026能被37整除。我們首先找到999=9*3*37，則原大整數(shù)應(yīng)該分拆成整1000的倍數(shù)，即末位開始切成3位一節(jié)，能簡化運算，判斷起來最容易，11026=11*1000+26=11*999+11+26,顯然原數(shù)能被37整除。

走筆至此，想起當(dāng)年小學(xué)奧數(shù)班黃老師講這個問題時，先介紹同余公式，再引出判斷方法。大家聽得懵懵懂懂，問題越來越多，聽課的人越來越少。但這種講課方法，才是名門正派的武功招式，學(xué)生沿著此思路能展開自己的研究和領(lǐng)悟。三十多年過去，學(xué)生還能記得解題思路，不敢忘記。