伪素数，又叫做伪质数：它满足费马小定理，但其本身却不是素数。最小的伪素数是341。有人已经证明了伪素数的个数是无穷的。事实上，费马小定理给出的是关于素数判定的必要非充分条件。若n能整除2^(n-1)-1，并n是非偶数的合数，那么n就是伪素数。第一个伪素数341 是萨鲁斯（Sarrus)在1819年发现的。

伪素数年表

伪素数的例子

伪素数的起源与研究

伪素数之谜

强伪素数

伪素数年表

1903年，马洛（Malo）证明：若n为伪素数，则<math>m=2^n-1</math>也是一个伪素数，从而肯定了伪素数的个数是无穷的。1950年，发现第一个偶伪素数161038=2*73*1103。

1951年，皮格（Beeger）证明了存在无限多个偶伪素数。

伪素数的例子

2^(5-1)-1=15,15|5. 2^(3-1)-1=3,3|3.但很多都是素数，如3，5，7，29，31……

1819年数学家萨鲁斯找到了反例：2^(341-1)-1|341,而341=11*31是合数，341就成了第一个伪素数。以后又发现了许多伪素数：561 645 1105 1387 1729……

伪素数的起源与研究

能整除a^n一a的合数n，a≥2，（a，n）=1，被称为以a为底的伪素数，简记为a-伪素数。

伪素数起源于17世纪法国数学家费马的某些研究。他于17世纪30年代末曾写信给法国数学家梅森，提到这样一个命题：2p一2能被素数p整除。后来，在他1640年10月18日给德贝西的信中说，他进一步证明了这样一个定理：

如果p是一个素数，且a不能被p整除，则ap-1－1能被P整除（等价的说法是ap－a能被素数p整除）。

后人称这个定理为费马小定理，以和费马大定理相区别。费马小定理奠定了现代数论中素数判定的基础。

按费马小定理，如果一个奇数n不能整除2n－2，则n必为合数（这是费马小定理的一个逆否命题）。但是，如果奇数n>1能整除2n－2， n就一定是素数吗？就是说，费马小定理的逆命题是否成立？对于1<n<300的数来说，计算可知，能整除2n－2的奇数n都是素数，这使得人们在很长的时间内认为费马小定理的逆命题当然成立。德国数学家莱布尼茨曾在1680年6月和1681年12月两次宣布他证明了这样一个命题：如果n不是素数，则2n－2不能被n整除（这是下述命题的逆否命题：如果2n－2能被n整除，则n是素数），但没发表他的证明。1742年4月，德国数学家哥德巴赫在给欧拉的信中表示要证明费马小定理的逆定理，但似乎也无结果。

1819年，法国数学家沙路斯发现，虽然341整除2341-2，但341是合数，341=11×31。这一反例表明费马小定理的逆定理不成立。1830年，一位匿名德国数学家指出更一般的构造反例的方法，他指出，只要能找到两个奇素数p和q，使它们的积pq能同时整除2p-1-1与2q-1-1，那么就可得到pq整除2pq-1-1。按此方法，人们发现除341外，还有561，645，1105，1389，1729，1905等也具有上述性质。于是，人们把能整除2n一2的合数n称为伪素数。1926年，普列特制成5000万以内的伪素数表，1938年他又推进上限到1亿，为此，有时伪素数亦被称为普列特数。

提出伪素数后自然就产生了类似素数的问题，并得到人们的研究。如伪素数有多少个？人们指出，伪素数有无穷多，1903年麦洛用一个构造性方法对此加以证明。他证明了，若n是奇伪素数，那么，n = 2n-1－1也是奇伪素数，我们已知有奇伪素数n0=341，按此法就可以构造出无穷多的奇伪素数来。再如是否存在偶伪素数?1950年，美国数学家D．H．莱默尔找到了第一个偶伪素数161038，161038=2×73×1103，73 |（2161038-2），1103 |（216038-2） 。1951年，荷兰的毕格尔又找到了一个偶伪素数，并证明了存在无穷多个偶伪素数。

后来人们针对费马小定理的一般情况，把伪素数概念一般化，就得出前面的定义。1904年，意大利数学家奇波拉给出一种构造a-伪素数的方法：

对于已知的整数a≥2，取p是任一奇素数，使p不能整除a（a2一1），则n=（a2p-1）/（a2-1）是a-伪素数。

他同时也证明了存在无穷多的一般伪素数。当然，在一般伪素数研究中，也有许多未解决的问题。例如，1952年杜帕克提出的，能否存在无穷多个伪素数，它们同时以2和3为底，或更一般些，能否存在无穷多个伪素数，它们同时以两个不同的整数a与b为底（a≥2，b≥2，且a与b不是同一个整数的幂）。

伪素数的一个用途是利用伪素数表来判定一个奇数n是否为素数，这是D．H．莱默尔提出来的：如果n不能整除2n-1－1，则据费马小定理知，n必为合数；如果n能整除2n-1－1，且n在伪素数表中，则n为合数，否则为素数。这种方法的关键就在于按伪素数表去掉伪素数，而这要求伪素数在能整除2n-1－1的数中相当少才行，这就是当n整除2n-1-1时，n是合数的比例问题。在前10亿个自然数中，共有50847534个素数，而只有以2为底的伪素数5597个，即在此范围内n整除2n-1－1产生合数的可能性只有0.011%。所以人们把整除2n-1-1的正整数n（>1）称为殆素数。在10亿之内，n整除2n-1－1同时整除3n-1－1的合数n只有1272个，即此时产生合数的可能性只有0.0025%。

如果存在合数n，对任何a>1，只要（a，n）=1时，n能整除an-1-1，则n被称为卡迈克尔数。这种数是由美国数学家R．D．卡迈克尔于1912年提出来的。最小的卡迈克尔数为561，这种数在自然数中更少了，在10亿之内，只有646个。一个问题就是：卡迈克尔数是否有无穷多？

伪素数之谜

享有"业余数学之王"称号的费马曾经证明:若p为素数,则a^p-a是p的倍数,进一步如果p与a互素,则显然a^(p-1)-1是p的倍数,用同余式来表达就是:

a^(p-1)=1 （mod p）

这个表达式无疑是数论大厦的一块基石.对如此美妙的定理如果毫不动心,那他一定是只剩下一口气的行尸走肉.推导这个公式用同余式最方便,由于与素数p互素的数有p-1个,它们是:

1,2,3,...p-1

显然有: a*2a*3a...a(p-1)=1*2*3...(p-1)（ mod p）

即: [a^(p-1)]*(p-1)!=(p-1)! （mod p）

因为从1到p-1之间的所有整数都于p互质，所以可以两边同除以(p-1)!得到:

a^(p-1)=1 （mod p）

再对a应用数学归纳法即可证明之.

但是它的逆定理是不成立的,即当a^(p-1)-1能被p整除时,p不一定是素数,在1819年,法国数学家莎路斯首先发现,虽然341能够整除2340-1,但是341=11*31为一个合数.后来有一位德国数学家一般性地证明了,只要找到两个奇素数p,q,使得它们的积能同时整除2^(p-1)-1,与2^（q-1）-1,就能保证pq整除2^(pq-1)-1.

伪素数有无穷多个,第一个证明这一点的是数学家迈罗在1903年给出的.如果n是伪素数,则2n-1也是伪素数,所以伪素数有无穷多个.除了上述的341之外,人们陆续发现了561,645,1105,1387,1729,1905等等.数学家普列特在1938年做出了1亿以内的伪素数表.因此伪素数又叫做普列特数.

除了奇伪素数以外,竟然还有偶伪素数存在,美国著名数学家D.H.莱默在1950年找到了第一个偶伪素数:161038,后来荷兰数学家毕格尔又发现了3个偶伪素数:215326,2568226和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亿个自然数中共有50847534个素数,而伪素数只有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)的分布情况.

x P(x) C(x)

1000 8 1

10000 22 7

100000 78 16

1000000 245 43

10000000 750 105

100000000 2057 255

1000000000 5597 646

10000000000 14887 1547

不超过100000的16个卡迈克尔数如下:

561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,62745,63973,75361

留给人们的未解之谜是;

(1) 同时以a,b为底的伪素数是否有无穷多个?

(2) 卡迈克尔数是否有无穷多个?

爱多士猜想有无限个卡迈克尔数，1994年 William Alford 、 Andrew Granville 及 Carl Pomerance 证明了这个命题.

强伪素数

令N=q1q2q3,q1<q2<q3是三因子的Carmicheal数,定义C3,1-及C3,2-数,它们分别指qi=5 mod 8,i=1,2,3及qi≡5 mod 8,i=1,2,q3≡9 mod 16时的情况,它们有着较高的成为强伪素数的概率.本文首先给出成为这些数的充分必要条件然后给出算法,最后经过上机计算得到1024以内的有58个对于前5个素数基的C3,1-强伪素数,其中有一个是对于前8个素数基的强伪素数;以及27个对前4个素数基的C3,2-强伪素数,只有一个是对于前4个基的强伪素数.