问题补充说明：这个问题十分深奥... 这个问题十分深奥 展开
伪素数之谜
享有"业余数学之王"称号的360问答费马曾经证明:若p为素数,则保料够查ap-a是p的倍数,进一步如果p与a互素,则显然ap-1-1是p的倍数,山担用同余式来表达就是:
ap-1=1modp
广六形这个表达式无疑是数论大厦的社矿染买案致否一块基石.对如此美妙的定理如果毫不动心,那他一定是只剩下一口气的行尸走肉.推导这个公式用同余式最方便,由于与素数p互素的数有p-1个,它们是:
1,2,3,...p-1
显然有:减约守探生a*2a*3a...a(p-1)=1*2*3...(附药开员茶课p-1)modp
即:ap-1*(p-1)!=(p-1)!modp
两边同除以(p-1)!得到:
ap-1=1modp
再对a应用数学归纳法即可证明之.
但是它的逆定理是不成立的,即多国曾销质穿门准当ap-1-1能被p整除时,p不一定是素数,在1819年,法国数学家莎路斯首先发现,虽然34胶差占宣居补矛律1能够整除2340-1,但是341=11*31为一个合数.后来有一位德国数学家一般性地证明了,只要找到两个奇素数p,q,使得它们的积能同时整除2p-1-1,与2q-1-1,就能保证pq整除2pq-1-1.
伪素数有无穷多个,第一个证明这一点的是数学家迈罗在1903年给出的.如果n是伪素数,则2n-1也是伪素数,所以伪素数有无穷多个.除了上述的341之外,人们陆续发现了561,645,1105,1387,1729,1905等等.数学家普列特在1日目938年做出了1亿以内的伪素若绿触回交吃数表.因此伪素数又叫做普列特数.
除了奇伪素数以外,竟然还有偶伪素数存在,美国著名数学家D.H.莱默在1950年找到了第一个偶伪素数:161038,后来荷兰数学家毕格尔又发现了3个偶伪素数:215326,25682史独26和143742226,并且从理论上证明了存在无穷多个偶伪素数.
伪素数是针对底数为2的情形提出的.而对于一般的底数a,则提出了a-伪素数的概念,例如91能整除390-1,所以把91称为3-伪素数.1904年,意大利数学家奇波拉给出了一种构造a-伪素数的方法:
对于已知的整数a>=2,取任意奇素数p,使得p不能整除a(a2-1),则n=(a2p-1)/(a2-1)必是a-伪素数.比如取a=2,选p=5,显然5不能整除2(22-1)=6,所以(210-1)/脱找束晚消益客入(22-1)=341是伪素数.
对于已知的整数a>=2,由于有无穷多个奇最逐曲素数不能整除a(a2-1),所以a-伪素数有无穷多个.
利用伪素数表,数学家岩弱提每那D.H.莱默建议按照如下程序来判别一个滑居片赵放革奇数是否是素数:如果p不能整除2p-1-供验氢句八者系1,则p必然为合数;如果p能整除2p-1-1,且p在伪素数表中,则p为合数,否则p为素数.显然这是基于费马小定理的检验法,沙短考零包征继银棉文括我想如果再结合筛法,就会完全剔除这些伪素数.
毕竟伪素数比较稀少,在前10亿个自然数中共有508雨47534个素数,而伪素数只有5597个,即大约只占万分之一.而同时能以2,3为底的伪素数只有1272个,即大约5万分之一.那么是否存在这样的数p,它能够整除所有的以2,3,4,...为底的费马表达式,那么p一定是素数了吧?遗憾的是,竟然存在这样的伪素数,它能够整除以任何整数a为底(即使是负整数)的ap-1-1,561就是最小的一个例子:
a560-1=(a2)280-1=(a2-1)(...)=(a10-1)(...)=(a16-1)(...)
由于561=3*11*17,而由费马小定理,3,11,17都能够整除上式,所以561也能够整除上式.这种极端的伪素数叫做绝对伪素数,又由于是首先由美国数学家卡迈克尔在1912年发现的,所以又叫做卡迈克尔数,为了判别什么样的整数是卡迈克尔数,他发现了一个准则:
如果整数n满足如下条件
(1)n没有平方因子,即n没有相同的素因子;
(2)n是奇数且至少有3个不同的素数因子;
(3)对于n的每一个素数因子p,p-1能够整除n-1;
则n必为卡迈克尔数.反之,如果n是卡迈克尔数,则n必满足上述3个条件.
1939年,数学家切尼克给出了一种构造卡迈克尔数的方法:
设m为自然数,且使得(6m+1),(12m+1),(18m+1)都是素数,则M3(m)=(6m+1)(12m+1)(18m+1)是具有3个素因子的卡迈克尔数.例如取m=1,则有M3(1)=7*13*19=1729是卡迈克尔数.类似地,自然数m是使得
Mk(m)=(6m+1)(12m+1)(9*2m+1)...(9*2k-2m+1)(k>=4)
中k个因子都是素数,则Mk(m)是含有k个素因子的卡迈克尔数.1985年,杜伯纳得到了下面一些巨大的卡迈克尔数:m=5*7*11*13*...*397*882603*10185时的含有3个素因子的卡迈克尔数M3(m)是一个1057位数,这是目前知道的最大的卡迈克尔数.其他的还有
m=323323*655899*1040/6时的M4(m)是个207位数的卡迈克尔数.
m=323323*426135*1016/6时的M5(m)是个139位数的卡迈克尔数.
m=323323*239556*107/6时的M6(m)是个112位数的卡迈克尔数.
m=323323*160*8033时的M7(m)是个93位数的卡迈克尔数.
1978年,约里纳戈发现了8个卡迈克尔数,它们都具有13个素数因子.这是目前所知道的含有素数因子最多的一组卡迈克尔数.下表是目前所知道的小于x的以2为底的伪素数个数P(x)与卡迈克尔数的个数C(x)的分布情况.
xP(x)C(x)
100081
10000227
1000007816
100000024543
10000000750105
1000000002057255
10000000005597646
10000000000148871547
不超过100000的16个卡迈克尔数如下:
561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,62745,63973,75361
留给人们的未解之谜是;
(1)同时以a,b为底的伪素数是否有无穷多个?
(2)卡迈克尔数是否有无穷多个?
强伪素数
令N=q1q2q3,q1＜q2＜q3是三因子的Carmicheal数,定义C3,1-及C3,2-数,它们分别指qi=5mod8,i=1,2,3及qi≡5mod8,i=1,2,q3≡9mod16时的情况,它们有着较高的成为强伪素数的概率.本文首先给出成为这些数的充分必要条件然后给出算法,最后经过上机计算得到1024以内的有58个对于前5个素数基的C3,1-强伪素数,其中有一个是对于前8个素数基的强伪素数;以及27个对前4个素数基的C3,2-强伪素数,只有一个是对于前4个基的强伪素数.
标签：素数
