Question

威尔逊定理逆定理成立么？？？

若p为质数，则p可整除(p-1)!+1称为威尔逊定理，它的逆定理成立么？如果成立，如何证明。如果不成立，举出反例。

Answer 1

1 定义 对整数a＞1，满足an≡a(modn)的合数n称为底为a的伪素数． 定理2．3 对每一个整数a＞1，有无限多个底为a的伪素数． 底为a的伪素数．我们有(a2－1)(n－1)=a2p－a2=a·(ap-1－1)(ap＋a)．由于ap与a的奇偶性相同，故2|ap＋a；又由费马小定理和pa得p|ap-1－1；由于p是奇数，则a2－1整除ap-1－1；而pa2－1，故有p(a2－1)|ap-1－1．因此，2p(a2－1)|(a2－1)(n－1)即2p|n－1．令n=1 ＋2pm。现在有a2p=n·(a2－1)＋1≡1(modn)．故an-1=a2pm≡1m=1(modn)．即an≡a(modn)，因此n是底为a的伪素数．由于对每个a＞1，满足p多个．因此，以a为底的伪素数有无限多个． 虽然底为2的伪素数有无限多个，但是，它们相对于素数而言是相当少的，隆德大学的波赫曼证明了小于1010×2的素数有882206716个，而塞尔弗来季和瓦格斯塔夫计算出底为2的伪素数在1到2×1010之间只有19865个．因此，在大多数情况下，我们的断言“如果2n≡2(modn)，则n是素数．”是正确的，用这个断言作素性判别，出错的概率很小，例如在n＜2×1010的范围内，出错的概率小于19865／(882206716 ＋19865)≈0.0000025．不过，这样的结果，在实际用来作素性判别时，用处不大，尽管它出错的概率很小，但它毕竟是会出错的．而且，对于特定的一个n，用上面的断言去判别它的素性，就不能排除错误就在此出现．(对于其它底a，可以作同样讨论．) 令人惊奇的是，存在这样的合数n，对任意的满足(a，n)=1的a＞1，n都是底为a的伪素数．这样的合数的存在是费马小定理的逆命题不成立的最合适的例证．因为它说明，即使对所有满足(a，n)=1的a有an-1≡1(modn)，仍不能断定n是素数．这样的合数是由卡米歇尔首先发现的，故叫卡米歇尔数． 例561是卡米歇尔数．这是卡米歇尔发现的第一个卡米歇尔数，也是最小的卡米歇尔数． 因为561=3×11×17，若gcd(a，561)=1， 则gcd(a，3)=gcd(a，11)=gcd(a，17)=1， 由费马小定理知，a2≡1(mod3)，a10≡1(mod11)，a16≡1(mod17)． 由于Lcm(2，10，16)=80， 故a80≡1(mod3)，a80≡1(mod11)，a80≡1(mod17)， 即得a80≡1(mod561)，故a500≡(a80)7≡17=1(mod561)． 所以561是卡米歇尔数． 一般地，我们有下面的定理． 定理2．4 (卡米歇尔)n是卡米歇尔数的充分必要条件是：i)n无平方因子；ii)n的每一个素因子p有p－1|n－1；iii)n是奇数且至少有三个不同的素因子． 证明 先证明充分性．设n满足条件i)， ii)， iii)，令n=p1p2…pk(k≥3)，p1，p2，…，pk是互不相同的奇素数． 现对任意的a＞1，若(a，n)=1，则(a，pi)=1， 由费马小定理得api-1≡1(mod pi)，i=1，2，…，k，而由条件ii)， 有Lcm(p1－1，p2－1，…，pk－1)|n－1，故得an-1≡1(modpi)(i=1，2，…，k)， 因而an-1≡1(modn)． 故n是卡米歇尔数． i=1，…，k．先证明n是奇数． 若n是偶数且含有一个奇素因子p． 这时，取a是p的奇原根， 由an-1≡1(modn)得an-1≡1(modp)． 因此，p－1|n－1，但p－1为偶数而n－1为奇数，这是不可能的． 又若n=2t，t＞1，取a=3，则(3，n)=1．1(mod2t)． 否则，，则， 但假设不符．故n必是奇数， 因而pi是奇素数，i=1，…，k．令gi是模piui的原根，i=1，…，k． 由中国剩余定理，可求 得a使a≡gi(modpiui)(i=1，…，k)．故gcd(a，n)=1． 因为n是卡米歇尔数，则an-1≡1(modn)，即有，an-1≡1(modpiui)，另一方面an-1≡gin-1(mod piui)，故有gin-1≡1(modpiui)．由原根的定义得φ(piui)|n－1，即是piui-1(pi－1)|n－1，i=1，…，k．而n－1=plu1…pkuk－1，故ui=1，i=1，…，k，因此，条件i)证得．又pi－1|n－1，i=1，…，k，即条件ii)证得．对iii)，若k＜3，由n是合数，则k=2，则有n=p1·p2(p1≠p2)，由于p1－1|p1p2－1，而p1p2－1=(p1－1)p2＋p2－1，故得p1－1|p2－1，同理可得，p2－1|p1－1，由此可得p1－1=p2－1，即p1=p2，这与假设不符，因而k≥3，即iii)证得． □ 例 由定理2.4可得2821=7·13·31，10585=5·29·73，27845=5·17·29·23，172081=7·13·31·61都是卡米歇尔数． 由于发现了卡米歇尔数，人们认识到利用费马小定理来作素性判别，不是件简单的事情．假如卡米歇尔数只有有限个，则可以给出一个上界M，这样，在n＞M的范围内对n作素性判别就变得容易起来．然而，卡米歇尔数可能有无限多个，这只是一个猜想，至今无人给出证明，但人们大都认为这个结果是正确的． 3．素性判别与广义黎曼猜想 1976年，缪内发现了素性判别与广义黎曼猜想(见附录)的一个深刻的关系．他得到的结果是：如果广义黎曼猜想(REH)成立，则有一个算法存在，它对每个n，可在log2n的多项式时间内判明n是否素数．即存在素性判别的多项式算法，而且可设计出这个算法． 这个关系的发现，也是以研究费马小定理为出发点的．下面熟知的欧拉的结果是费马小定理的推广． 定理2.11 若n是一个奇素数，则对任意的自然数a，na有 1976年初，勒默发表了一篇短小精悍的文章，证明了定理1的逆定理也成立，他得到了． 定理2.12 (勒默) 若n是奇合数，则存在自然数a，满足(a， 证明 若n含有因子pα，p是奇素数，α＞1．取a为pα的原根， 若n=p1p2…Pt，t≥2，P1，P2，…，Pt为互不相同的奇素数．由 即2≡0(modp2)，但p2是奇素数．这是不可能的．故必有a使(a， 尽管勒默的这个结果说明了，若n是合数，则在1到n之间到少存 也没有指明a在何处．对某个数n，当然，我们可以对1到n之间的每 这个计算量太大了．因此，我们希望能够改进勒默的这个结果．如果对 时只要对较少的a检验．这样就可望得出较有效的素性判别法． 缪内注意到，给定一个数n，在n的缩系组成的群Un={a(modn) 全体构成一个子群，设其为Mn．于是就可以利用下面的安克尼和蒙特哥梅利的结果． 定理2.13 (安—蒙)在广义黎曼猜想(REH)成立的条件下．存在一个常数C，对任何自然数n及Un到任何一个群G的非单位同态ψ，都存在q使1＜q≤C(log2n)2且ψ(qmodn)≠1(其中1是G的单位元)． 由此，缪内得到了下面的结果： 定理2.14 (缪内)在广义黎曼猜想的成立之前提下，存在一个常数C，对任何的自然数n，若n是合数，则存在1≤a≤C(logn)2 Un到Un的同态映射．因为n是合数，由定理2.12知，ψ不是单位同态映射．因此，由定理2.13，存在a使1＜a≤C(log2n)2使ψ(amodn) 注 定理2.14中的常数C可取作与定理2.13中的C相同． 维路于1978年指出，定理2.14中的常数C可以定为70． 由定理2.14，我们说，在广义黎曼猜想成立的前提下，素数判别的多项式算法是存在的．我们可以如下设计出这样一个算法： (modn)是否成立．若对其中的一个a成立，则停止检验，这时n是合数(由定理2.11)，若对每一个a都不成立，也就是说，对a=1，2，…， 上述算法可以完全确定地判别n是否素数， 其计算量就是作70 即工作量是O(log25)，因而这是一个多项式算法． 由此可见，只要广义黎曼猜想成立，则素性判别的多项式算法是找到了的．但证明广义黎曼猜想是相当困难的，这是数学家们一直关注的问题．这里的讨论也表明，素性判别是需要用较高深的方法来研究． 本文来自CSDN博客，转载请标明出处： http://blog.csdn.net/zhouq1986/archive/2008/04/06/2254784.aspx

记得采纳啊