美文网首页
数的整除性判断

数的整除性判断

作者: ismowang | 来源:发表于2020-08-20 11:50 被阅读0次

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

    如何判断一个大整数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整除。

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

    相关文章

      网友评论

          本文标题:数的整除性判断

          本文链接:https://www.haomeiwen.com/subject/cdesjktx.html