查看“︁Fermat 伪质数”︁的源代码

[[分类:整除理论]]
[[分类:同余理论]]
[[分类:以 Fermat 命名]]
{{InfoBox
|name=费马伪素数
|eng_name=Fermat pseudoprime
|aliases=费马伪质数,伪素数,伪质数,Fermat pseudoprime number
}}
{{InfoBox
|name=以 2 为底的费马伪素数
|eng_name=Fermar pseudoprime to base 2
|aliases=萨鲁斯数,Sarrus number,波里特数,Poulet number,伪素数,伪质数
}}
{{InfoBox
|name=绝对伪素数
|eng_name=Carmichael number
|aliases=卡迈克尔数,绝对伪质数,绝对费马伪素数,绝对费马伪质数,absolute Fermat pseudoprime
}}
[[Fermat 小定理|<ins>费马</ins>小定理]]对全体质数和小部分合数成立，对应的[[伪素数]]被称为'''费马伪素数'''/'''费马伪质数'''('''Fermat pseudoprime''')。

根据<ins>费马</ins>小定理中的 <math>a</math> 的取值，称为以 <math>a</math> 为底的<ins>费马</ins>）伪素数/<ins>费马</ins>伪质数。

特别地，以 2 为底的<ins>费马</ins>伪质数有时也被称为<ins>萨鲁斯</ins>数或<ins>波里特</ins>数。

<blockquote>
中文语境中，'''伪素数'''/'''伪质数'''经常指<ins>费马</ins>伪质数或其中以 2 为底的<ins>费马</ins>伪质数（<ins>萨鲁斯</ins>数/<ins>波里特</ins>数）。此时以任意 <math>a</math> 为底的称为 <math>a</math>-伪素数/ <math>a</math>-伪质数。
</blockquote>

若对任意互质的 <math>a</math> 都是<ins>费马</ins>伪素数，称为'''绝对（<ins>费马</ins>）伪素数'''('''absolute Fermat pseudoprime''')或'''<ins>卡迈克尔</ins>数'''('''Carmichael number''')。

== 定义 ==

对整数 <math>n</math> ，若 <math>n</math> 为合数，且：
* 存在整数 <math>a</math> 使得 <math>n \mid a^n - a</math> （或等价地， <math>n \mid a^{n-1} - 1</math> ），称整数 <math>n</math> 是以 <math>a</math> 为底的'''（<ins>费马</ins>）伪素数'''/'''（<ins>费马</ins>）伪质数'''('''Fermat pseudoprime''' to base <math>a</math>) ；
* 对任意与 <math>n</math> 互质的 <math>a</math> 都有 <math>n \mid a^n - a</math> （或等价地， <math>n \mid a^{n-1} - 1</math> ），称整数 <math>n</math> 是'''绝对伪素数'''/'''绝对伪质数'''或'''<ins>卡迈克尔</ins>数'''('''Carmichael number''')。

特别地，以 2 为底的'''（<ins>费马</ins>）伪素数'''/'''（<ins>费马</ins>）伪质数'''也称为<ins>萨鲁斯</ins>数(Sarrus number)或<ins>波里特</ins>数(Poulet number)。

== 性质 ==

若 <math>n</math> 是<ins>费马</ins>伪素数，则 <math>2^n-1</math> 也是<ins>费马</ins>伪素数。

== 举例 ==

最小的<ins>萨鲁斯</ins>数是 <math>341</math> ，构成数列为{{OEIS|A001567}}。

以 1 为底的<ins>费马</ins>伪质数是全体合数。以3、5、6、7、10为底的<ins>费马</ins>伪质数，构成数列为{{OEIS|A005935}}~{{OEIS|A005939}}，以4、8、9、11~100为底的，见{{OEIS|A020136}}~{{OEIS|A020228}}。

最小的<ins>卡迈克尔</ins>数是 <math>561</math> ，构成数列为{{OEIS|A002997}}。


{{整除与质数}}

== 琐事 ==

=== 名称 ===

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

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

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