伪素数的充要条件

定义 若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是合数,