Fermat 伪质数

费马伪素数
术语名称	费马伪素数
英语名称	Fermat pseudoprime
别名	费马伪质数, 伪素数, 伪质数, Fermat pseudoprime number

以 2 为底的费马伪素数
术语名称	以 2 为底的费马伪素数
英语名称	Fermar pseudoprime to base 2
别名	萨鲁斯数, Sarrus number, 波里特数, Poulet number, 伪素数, 伪质数

绝对伪素数
术语名称	绝对伪素数
英语名称	Carmichael number
别名	卡迈克尔数, 绝对伪质数, 绝对费马伪素数, 绝对费马伪质数, absolute Fermat pseudoprime

Fermat 测试依据 Fermat 小定理区分正整数中的质数与合数，这一标准中判定为合数的标准只对合数成立，但判定质数的标准对全体质数和小部分合数成立，这些被误判的合数就是 Fermat 测试所对应的伪质数，称为 Fermat 伪质数(Fermat pseudoprime)。

根据 Fermat 小定理中的 [math]\displaystyle{ a }[/math] 的取值，称为以 [math]\displaystyle{ a }[/math] 为底的 Fermat 伪质数。

特别地，以 2 为底的 Fermat 伪质数也被称为 Sarrus 数或 Poulet 数。

中文语境中：

不少材料中，伪质数一词可能默认仅包含 Fermat 伪质数。

不少材料中，伪质数一词可能默认仅包含以 2 为底的 Fermat 伪质数（Sarrus 数/ Poulet 数）。这些材料中将以任意 [math]\displaystyle{ a }[/math] 为底的 Fermat 伪质数称为 [math]\displaystyle{ a }[/math]-伪质数。

若一个正整数对任意互质的 [math]\displaystyle{ a }[/math] 都是 Fermat 伪素数，称为绝对伪素数/绝对 Fermat 伪素数(absolute Fermat pseudoprime)或 Carmichael 数(Carmichael number)。

定义

对整数 [math]\displaystyle{ n }[/math] ，若 [math]\displaystyle{ n }[/math] 为合数，且：

存在与 [math]\displaystyle{ n }[/math] 互质的整数 [math]\displaystyle{ a }[/math] 使得 [math]\displaystyle{ n \mid a^n - a }[/math] （或等价地， [math]\displaystyle{ n \mid a^{n-1} - 1 }[/math] ），称整数 [math]\displaystyle{ n }[/math] 是以 [math]\displaystyle{ a }[/math] 为底的 Fermat 伪质数(Fermat pseudoprime to base [math]\displaystyle{ a }[/math]) ；
对任意与 [math]\displaystyle{ n }[/math] 互质的 [math]\displaystyle{ a }[/math] 都有 [math]\displaystyle{ n \mid a^n - a }[/math] （或等价地， [math]\displaystyle{ n \mid a^{n-1} - 1 }[/math] ），称整数 [math]\displaystyle{ n }[/math] 是绝对伪质数/绝对 Fermat 伪质数或 Carmichael 数(Carmichael number)。

特别地，以 2 为底的 Fermat 伪质数也称为 Sarrus 数(Sarrus number)或 Poulet 数(Poulet number)。

性质

若 [math]\displaystyle{ n }[/math] 是以 2 为底的 Fermat 伪质数，则 [math]\displaystyle{ 2^n-1 }[/math] 也是以 2 为底的 Fermat 伪质数。

举例

以 1 为底的 Fermat 测试是平凡的，全体合数都满足条件，没有鉴别意义。

以 2 为底的 Fermat 伪质数中，最小的数是 [math]\displaystyle{ 341 }[/math] ，构成数列为 OEIS-A001567。

以 3、5、6、7、10 为底的 Fermat 伪质数，构成数列为 OEIS-A005935~OEIS-A005939 ，以 4、8、9、11~100 为底的 Fermat 伪质数，构成数列为 OEIS-A020136~OEIS-A020228 。

最小的 Carmichael 数是 [math]\displaystyle{ 561 }[/math] ，构成数列为 OEIS-A002997 。

整除理论
整除关系	整除、倍数、因数		带余除法
正整数的分类	1、质数、合数
正整数的分类	质数测试	试除法、 Fermat 测试	Eratosthenes 筛法、 Euler 筛法
最大公约数理论	公倍数、最小公倍数 [math]\displaystyle{ \operatorname{lcm} }[/math]、公因数、最大公因数 [math]\displaystyle{ \operatorname{gcd} }[/math]		辗转相除法
最大公约数理论	互质
算术基本定理	算术基本定理		标准质因数分解

琐事

名称

萨鲁斯数的名称来自第一个计算出第一个以 2 为底的费马伪质数，也是第一个发现费马伪质数存在的数学家。

波里特数的名称来自第一个编制出 5000,0000 以内，及 1,0000,0000 以内全部以 2 为底的费马伪质数的数学家。

卡迈克尔数的名称来自第一个提出存在满足绝对费马伪质数的性质的数学家。