Fermat 伪质数
| 费马伪素数 | |
|---|---|
| 术语名称 | 费马伪素数 |
| 英语名称 | Fermat pseudoprime |
| 别名 | 费马伪质数, 伪素数, 伪质数, Fermat pseudoprime number |
| 以 2 为底的费马伪素数 | |
|---|---|
| 术语名称 | 以 2 为底的费马伪素数 |
| 英语名称 | Fermar pseudoprime to base 2 |
| 别名 | 萨鲁斯数, Sarrus number, 波里特数, Poulet number, 伪素数, 伪质数 |
| 绝对伪素数 | |
|---|---|
| 术语名称 | 绝对伪素数 |
| 英语名称 | Carmichael number |
| 别名 | 卡迈克尔数, 绝对伪质数, 绝对费马伪素数, 绝对费马伪质数, absolute Fermat pseudoprime |
费马小定理对全体质数和小部分合数成立，对应的伪素数被称为费马伪素数/费马伪质数(Fermat pseudoprime)。
根据费马小定理中的 [math]\displaystyle{ a }[/math] 的取值，称为以 [math]\displaystyle{ a }[/math] 为底的费马）伪素数/费马伪质数。
特别地，以 2 为底的费马伪质数有时也被称为萨鲁斯数或波里特数。
中文语境中，伪素数/伪质数经常指费马伪质数或其中以 2 为底的费马伪质数（萨鲁斯数/波里特数）。此时以任意 [math]\displaystyle{ a }[/math] 为底的称为 [math]\displaystyle{ a }[/math]-伪素数/ [math]\displaystyle{ a }[/math]-伪质数。
若对任意互质的 [math]\displaystyle{ a }[/math] 都是费马伪素数，称为绝对（费马）伪素数(absolute Fermat pseudoprime)或卡迈克尔数(Carmichael number)。
定义
对整数 [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 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] 是绝对伪素数/绝对伪质数或卡迈克尔数(Carmichael number)。
特别地，以 2 为底的（费马）伪素数/（费马）伪质数也称为萨鲁斯数(Sarrus number)或波里特数(Poulet number)。
性质
若 [math]\displaystyle{ n }[/math] 是费马伪素数，则 [math]\displaystyle{ 2^n-1 }[/math] 也是费马伪素数。
举例
最小的萨鲁斯数是 [math]\displaystyle{ 341 }[/math] ，构成数列为A001567。
以 1 为底的费马伪质数是全体合数。以3、5、6、7、10为底的费马伪质数，构成数列为A005935~A005939，以4、8、9、11~100为底的，见A020136~A020228。
最小的卡迈克尔数是 [math]\displaystyle{ 561 }[/math] ，构成数列为A002997。
| 整除理论 | ||
|---|---|---|
| 整除关系 | 整除、倍数、因数 | 带余除法 |
| 正整数的分类 | 1、质数、合数 | |
| 质数测试 | 试除法、埃氏筛、线性筛 | |
| 最大公约数理论 | 公倍数、最小公倍数 [math]\displaystyle{ \operatorname{lcm} }[/math]、公因数、最大公因数 [math]\displaystyle{ \operatorname{gcd} }[/math] | 辗转相除法 |
| 互质 | ||
| 算术基本定理 | 算术基本定理 | 标准质因数分解 |
琐事
名称
萨鲁斯数的名称来自第一个计算出第一个以 2 为底的费马伪质数，也是第一个发现费马伪质数存在的数学家。
波里特数的名称来自第一个编制出 5000,0000 以内，及 1,0000,0000 以内全部以 2 为底的费马伪质数的数学家。
卡迈克尔数的名称来自第一个提出存在满足绝对费马伪质数的性质的数学家。