第22卷 第2期
2004年4月
运城学院学报
Journal of Yuneheng University
V01．22 NO．2
Apr．2004
伪素数——绝对伪素数的分析与探求
王 琦，解建国
(运城学院计算机科学与技术系．山西运城044000)
摘 要：伪素数的提出及研究成果，使素数的研究进入到一个更加丰富的界面，使它成为研究素数的一种方
法。文章在证明了伪素数有无穷多的同时．还给出了由其引出的绝对伪素数的求解方法。
关键词：素数；伪素数；绝对伪素数
中图分类号：0187．1文献标识码：A 文章编号：1008—8008(2004)02–0012—02
由费尔玛(Fermat)小定理引出的伪素数，是素数
研究中的重要成果，是数论研究中很有价值的“副产
品”，由其又引出的绝对伪素数，目前仍在探索之中，下
面给予总结，并试图给出寻求的计算机方法。
一、关于伪素数
1．伪素数的提出
伪素数是假素数，实际上它是合数，但是它必须是
由费尔玛小定理得出的。下面叙述并给予必要的证
明。
费尔玛小定理 若p为素数，则口p—a是P倍数。
如果再满足P与a互寒，则口P1一l是P的倍数。
费尔玛小定理的强化结论用同余式来表达就是：
a,’–1三1 rood(p) (1)
(1)式是数论之精华，它可以这样证明：
因为P l口p—a，即：户}a(ap-1—1)，因为P与a互
素，所以有：P I口扩1—1，即是：口卜1三1 mod(p)。
但是，当声与a互紊，且口扩1一l能被p整除时，P
不一定是素数。若这时户不是素数，那么它就叫伪素
数。再考虑到a的取值，就叫a一伪素数。通常所说的伪
素数是2一伪素数。
比较简单的一个伪素数是341，虽然341能够整除
2340—1，但341；11·3l是一个合数。
2．伪素数有无穷多的一种证明方法
素数有无穷多个，而伪素数也有无穷多个，我们
有：
定理 如果行是伪素数，则2n—l也是伪素数，所
以伪素数有无穷多个。
定理中的伪素数聍是2一伪素数，如果2一伪素数
有无穷多个，由伪素数的定义，当然伪素数也就有无穷
多个。证明如下：
根据伪素数的定义，2一一l与2互素是显然的，只
需证明两个问题：第一要证明2一一1 221～1 1 1；第二
要证明2n—l可分解因数。
先证明第一个问题。事实上，因n是伪素数，所以挖
I 2—1一l，因此可设2—1—1一勋，这里k为某一个确
定的整数。由于：
221—1—1—1=221—2—1=2Z(2”1一1)一1=
(22一一1)2—1=(22一一1—1)(22一一1+1)一(2h一
1)(2k-+1)=[(2一)‘一1](2蛔+1)。因为：(2一)‘一1=
(2一一1)[(2一)卜1+(2n)。卜2+⋯2一+1]，所以有：2”一
1 221—1—1—1。
其次证2一一1可分解因数。事实上，因，z是伪素数，
所以可设7l；h·l(h和Z均大于2)，这样有：2n—l；
2Ⅳ一1=(2h)f一1=(2h—1)[(2h)卜1+(2h)l–2+
⋯26+1]。
这就证明了2一一l是合数，所以它是伪素数。考虑到迭
代原理，便知伪素数有无穷多个。
实际上，以2为底的伪素数除了341以外，还有
561，645，1105，1387等。
前面提到的伪素数，由于其底数为2，所以它们都
是奇伪素数，实际上还存在着偶伪素数，当然它们的底
数不能是2，并且已证明偶伪素数也有无穷多个，这里
不赘述。
伪素数研究的主要对象是2一伪素数，对于a≠2
的伪素数，研究起来方法相似，但逐一研究很显繁琐，
在此仅举一例说明。例9l能