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

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

威尔逊定理逆定理成立么?若p为质数,则p可整除(p-1)!+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
记得采纳啊