伪素数 伪素数是指满足某种素数性质但实际上不是素数的正整数。这个概念在素性测试中尤为重要，因为许多测试基于某个与素数相关的条件，但该条件可能被某些合数满足。 1. 费马小定理与费马伪素数 费马小定理指出：如果 \( p \) 是素数，且 \( a \) 是与 \( p \) 互质的整数，则 \( a^{p-1} \equiv 1 \pmod{p} \)。 然而，存在一些合数 \( n \)，使得对于某个与 \( n \) 互质的 \( a \)，有 \( a^{n-1} \equiv 1 \pmod{n} \)。这样的 \( n \) 称为以 \( a \) 为底的费马伪素数。 例如，\( n = 341 = 11 \times 31 \) 是以 2 为底的费马伪素数，因为 \( 2^{340} \equiv 1 \pmod{341} \)，但 341 是合数。 2. 卡迈克尔数（绝对费马伪素数） 如果合数 \( n \) 对于所有与 \( n \) 互质的 \( a \) 都满足 \( a^{n-1} \equiv 1 \pmod{n} \)，则称 \( n \) 为卡迈克尔数。 卡迈克尔数是费马伪素数的一种极端情况，它们能通过所有以互质底数为基础的费马测试。 最小的卡迈克尔数是 561，满足 \( a^{560} \equiv 1 \pmod{561} \) 对所有与 561 互质的 \( a \) 成立。 3. 其他类型的伪素数 欧拉伪素数 ：基于欧拉准则的伪素数。如果 \( n \) 是奇合数，且对于某个与 \( n \) 互质的 \( a \)，有 \( a^{(n-1)/2} \equiv \left( \frac{a}{n} \right) \pmod{n} \)（其中 \( \left( \frac{a}{n} \right) \) 是雅可比符号），则 \( n \) 是以 \( a \) 为底的欧拉伪素数。 强伪素数 ：基于米勒-拉宾素性测试的伪素数。如果 \( n \) 是奇合数，且能通过以 \( a \) 为底的米勒-拉宾测试，则称 \( n \) 是以 \( a \) 为底的强伪素数。强伪素数比费马伪素数更罕见。 4. 伪素数的意义与应用 伪素数的存在表明，基于单一条件的素性测试（如费马测试）可能产生误判，因此需要更可靠的算法（如米勒-拉宾测试或AKS算法）。 研究伪素数的分布有助于理解数论中的深层结构，例如与黎曼猜想相关的性质。