伪素数的充要条件

定义 若2n-1-1≡0 （modn）,且n为合数,则称n是伪素数。 伪素数的个数无限,种类无穷,它们隐藏在自然数集合之中,使得费马定理的逆命题不真。目前,人们还不能找出自然数集里所有的伪素数. 文[1]、[2]给出了两个不同类型的伪素数的表达。本文中,我们证明如下的 定理 n是伪素数的充要条件是 n为合数,且n|2n-1,y（n）-1. 其中φ（n）是欧拉函数,（n-1,φ（n））是n-1与φ（n）的最大公约数。 证 1.设n是伪素数,则依据定义得知2n-1-1=0 （modn）,且n是合数,

一类具有费马性质的合数

若a不能被素数p整除时,则 ap-1=1 （mod p） （1） 这是著名的费马定理,其应用很广。但是它的逆命题不成立。 我国古代（大约2600年前）曾出现一个错误的命题:若n|2n-2,则n是一个素数。 这个错误的观点,持续了很长一段时期,直到1819年才有人找出一个反例,即341|2341-2,但341=11·31不是素数。从此,更多的反例被找出,例如561,645等等。