龙空技术网

素数通项公式的先导一—威尔逊素数判定法的证明和简化及计算

王庆元61292207 302

前言:

目前小伙伴们对“判断素数为什么要开平方”大概比较珍视,看官们都想要知道一些“判断素数为什么要开平方”的相关内容。那么小编也在网上汇集了一些有关“判断素数为什么要开平方””的相关知识,希望小伙伴们能喜欢,同学们快快来了解一下吧!

最近有文章报导、世界数学界在整理、汇总几百年来的数学文献时、发现了1770年由数学家威尔逊提出的一个素数判别法则:如果P是素数、那么(P-1)!+1就一定能被P整除。不知何种原因、是文稿失落还是当时就没有详细资料、有关证明无从考证。网友们在网上见到此消息后、也进行了具体实例的检验、证实此判别法则的正确、并要求提供具体证明方法及过程对此判别法给以确认。

这个素数判定法确是当前所知的各类判定法中最简捷的表达式、可算性强、极有可能是素数通项公式的先导、拓展性强。下面展示其内涵。 (P-1)!+1=(P-1)(P-2)(P-3)……3×2×1+1。展开后立即可以得出一个结论: [(P-1)!+1]/P 式中P必须是素数、因为如果P是合数、假设P=ab、(a>1、b>1、a、b∈N*)、而P是(P-1)的后续数也就是P只比(P-1)大了1、所以a、b两个因子必定在(P-1)的所有前继数中、所以(P-1)!一定能被P整除。即[(P-1)!+1]/P=n+1/P、(n∈N*),完全失去了要证明的意义,这说明P决不可为合数、所以P是素数是本题证明的必要条件 。威尔逊法则本质上是应用了素数定义、即素数只可能被1和自身整除、不能被其它自然数整除、而确立的判别式;它避开了判断一个素数P要运用√P内各正整数一个一个去除以被判定数是否素性的除法筛法原理、而用自然数的阶乘、从而再应用余数定理、简化了计算而以。要证明命题、(P-1)!是关键。(P-1)!=(P-1)(P-2)(P-3)…….[P-(P-1)/2]{P-[P-(P-1)/2]}……[P-(P-3)][P-(P-2)][P-(P-I)]。也就是下述公式表示。(在理解证明时除了吃透余数定理,还应理解(P-n)除以P的余数与[P-(P-n)]除以P的余数是相同的。所以最后才可能出现自然数的平方。)

n=1:(P-1)[P-(P-I)] =(P-1)×1=-1

n=2:(P-2)[P-(P-2)]=(P-2)×2=-4

n=3:(P-3)[P-(P-3)]=(P-3)×3=-9

n=4:(P-4)[P-(P-4)]=(P-4)×4=-16

n=5:(P-5)[P-(P-5)]=(P-5)×5=-25

n=(P+1)/2:[P-(P-1)/2]{P-[P-(P-I)/2]}=[P-(P-1)/2][(P-1)/2]=-(P-1)(P-1)/4。(以n=2为例、显示应用乘法余数定理过程。相乘去括号:PxP、P×[-(P-2)]、-2P、(-2)[-(P-2)]。显见前面三项都含有P因子均能被P整除、只有第四项再去括号应用余数定理得到余数为-4。)

上述各项化简后、应用乘法余数定理、得到负的各自然数的平方、以及-(P-1)(P-1)/4。

从上式可以看出该公式虽然是一个不定的形态、但是对任何一个素数P都是适用的.而且只有P是某个具体数值时、同时也就限定了n的最大值、才能体现即证明它的正确性。试代入几个素数验证。P=5:最大项(P-1)/2=2,共计二项:(-1)平方为1。(P-1)!+1=4×1+1=5、能被P整除。P为7、验证计算:最大项n=P-1/2=3,应用公式.(-1)的三次方为-1。-1×1×4×9=-36被7整除后为-1、所以(P-1)!+1=-1+1=0能被7整除。最后再验证13这个素数:n最大值为13-1/2=6、即在公式中(-1)的6次方为1。(P-1)!+1=1×1×4×9x16×25×36应用余数定理各数被13除得的余数再相乘=10×3x12×10=30X120=4X3=12,所以(P+1)!+1=12x1+1=13能被13整除。综上所述威尔逊素数判定法可以进一步演化成为便于计算的形式:

上式中P为素数。n∈N*。C∈±N。三点说明:1、威尔逊原判定法中是不可能出现负数的、此公式出现负自然数平方的原因是我们应用了乘法余数定理,已舍去了被P整除的各部分、而舍去的整除部分其数值是远大于公式中显示的负值的、总体必是正值。2、上述公式是威尔逊原式通过应用乘法余数定理后演化生成、所以会出现c=0的现象、(P-1)!/P应用余数定理后成为余数为-1、但公式中还要加1使结果为零、即加1后没有余数、也就表示被P整除了。3、公式中体现了素数P在判定中只与(P-1)/2的所有自然数平方有关联、显示了素数与它有关的自然数平方的内在联系。实际上、上述公式就是:

最后从数理逻辑上证明威尔逊法则:(P-1)!=(P-1)(P-2)(P-3)……[P-(P-3)][P-(P-2)][P-(P-1)]应用乘法余数定理各项除以P得(-1)(-2)(-3)……[-(P-3)][-(P-2)][-(P-1)]。因为(P-1)!展开必定具有偶数项、所以上式中负号均负负得正全部取消。显而易见(P-1)!在运用余数定理除以P以后还是等于(P-1)!我想试图证明威尔逊法则的每个人都碰到过这个循环而无法进行下去;所以必须另辟蹊径。

必须运用同余概念。整数a、b、两数分别被自然数m去除、若a的余数与b的余数相同、则称a、b、对于模m、同余、即a≡b、(modm)。两个同余教a、b的一个重要性质:a、b对于模m同余、则a-b一定能被m整除。很好理解:a-b时、a与b同余、则余数被减去、Sm-tm一定被m整除。运用此性质证明本题:假设(P-1)!+1能被素数P整除、而P!当然也能被P整除、这样就找到了两个整数a、b.即P!、[(P-1)!+1],都能被P整除、即两整数modP同余、余数都为零。那么a-b即P!-[(P-1)!+1]=(P-1)!(P-1)-1、运用余数定理后原式=-(P-1)!-1=-[(P-1)!+1]、可见方括号也能被P整除、完全附合同余定律的要求、所以(P-1)!+1能被P整除的假没是正确的。威尔逊法则被证明。

标签: #判断素数为什么要开平方 #为啥判断素数要开平方