题目

初等数论伪素数的定义为什么不带p不整除a,感觉不恰当?费马小定理原话是“若p是素数,且p不整除a,则a∧p-1≡1(mod p)”,显然我认为人们好奇的是当p不整除a且a∧p-1≡1(mod p)是p也可能为合数（人们希望此时p为素数）,此时p称作伪素数,为什么伪素数的定义中没有要求p不整除a呢?因为如果不要求p不整除a的话根本满足不了费马小定理的条件,就算p是素数,也得不到a∧p-1≡1(mod p),何谈我上述的“好奇”呢,请明白我意思的高高手讲讲

提问时间：2021-03-27

答案

费马小定理给出的是关于素数判定的必要非充分条件.若n能整除2^(n-1)-1,并n是非偶数的合数,那么n就是伪素数.第一个伪素数341 是萨鲁斯（Sarrus)在1819年发现的.