数的整除性判断

数的整除性判断的通用公式

如何判断一个大整数N能被某个特定的质数p整除，

XES老师让大家直接背以下结论：

判断能被2、5整除，看个位；判断能否被3、9整除，看各数位和能否被3、9整除； 等等。

我们尝试用逐步逼近的推理给出一个判断此类问题的通用办法。比如判断11026能否被37整除，我们也能很快得到答案。理解以下推理，我们对同余方程的用到的定理也有更深的了解。

1、  判断能被10整除，直接看个位。12345被10除，余数是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，实际上我们已经完成了所有偶数质数（以及5）的整除性判断。以下我们就可以关注奇素数（除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的余数就好了。

以上是对10附近两个奇数整除性判断的方法  。关键是利用10^m余数特点简化计算。

6、  由4和5两条，我们发现判断N能否被奇素数整除，关键是10^m-1能否被p整除。

7、  由此我们探求的目标就是求10^m模p余1的同余方程求解。

8、  原根的概念。数论中费马小定理和推广的欧拉定理。

9、  由此，我们可以归纳出任何质数p的最优化的整除判定方法。对于给定的N和p，我们先找到使得10^m-1能够被p整除的m。我们就能将大整数截成m位的小整数进行同余计算。

回到我们的例子，如何判断11026能被37整除。我们首先找到999=9*3*37，则原大整数应该分拆成整1000的倍数，即末位开始切成3位一节，能简化运算，判断起来最容易，11026=11*1000+26=11*999+11+26,显然原数能被37整除。

走笔至此，想起当年小学奥数班黄老师讲这个问题时，先介绍同余公式，再引出判断方法。大家听得懵懵懂懂，问题越来越多，听课的人越来越少。但这种讲课方法，才是名门正派的武功招式，学生沿着此思路能展开自己的研究和领悟。三十多年过去，学生还能记得解题思路，不敢忘记。