卡迈克尔数 卡迈克尔数是一类特殊的合数，满足以下性质：对于任意与 \( n \) 互质的整数 \( a \)，都有 \[ a^{n-1} \equiv 1 \pmod{n} \] 这与费马小定理对素数的描述一致，但卡迈克尔数本身是合数，因此被称为“伪素数”。 1. 费马小定理与伪素数 费马小定理 ：若 \( p \) 是素数，且 \( \gcd(a, p) = 1 \)，则 \[ a^{p-1} \equiv 1 \pmod{p}. \] 费马伪素数 ：若合数 \( n \) 对某个 \( a \)（满足 \( \gcd(a, n) = 1 \)）使得 \( a^{n-1} \equiv 1 \pmod{n} \)，则称 \( n \) 为以 \( a \) 为底的伪素数。 但卡迈克尔数更强：它对所有与 \( n \) 互质的 \( a \) 均满足此同余式。 2. 卡迈克尔数的定义与性质 定义 ：合数 \( n \) 是卡迈克尔数，当且仅当： \( n \) 无平方因子（即 \( n = p_ 1 p_ 2 \cdots p_ k \)，各 \( p_ i \) 为互异奇素数）； 对每个素因子 \( p_ i \)，均有 \( p_ i - 1 \mid n - 1 \)。 例 ：最小的卡迈克尔数是 \( 561 = 3 \times 11 \times 17 \)。 检查条件： \( 3-1=2 \mid 560 \)， \( 11-1=10 \mid 560 \)， \( 17-1=16 \mid 560 \)。 3. 为什么卡迈克尔数满足费马性质？ 设 \( n = p_ 1 p_ 2 \cdots p_ k \)，且 \( \gcd(a, n) = 1 \)。对每个 \( p_ i \)，由费马小定理： \[ a^{p_ i - 1} \equiv 1 \pmod{p_ i}. \] 由于 \( p_ i - 1 \mid n-1 \)，可写 \( n-1 = m_ i (p_ i - 1) \)，于是 \[ a^{n-1} = (a^{p_ i - 1})^{m_ i} \equiv 1^{m_ i} = 1 \pmod{p_ i}. \] 这对所有素因子 \( p_ i \) 成立，由中国剩余定理（模数两两互质），得 \[ a^{n-1} \equiv 1 \pmod{n}. \] 4. 卡迈克尔数的存在性与密度 存在性 ：1910 年卡迈克尔发现 \( 561 \) 是第一个这样的数。 无穷性 ：1994 年 Alford、Granville 和 Pomerance 证明存在无穷多个卡迈克尔数。 密度 ：卡迈克尔数比素数稀疏，但数量仍无穷。在 \( x \) 以内的卡迈克尔数数量约为 \( x^{1/3} \) 级别。 5. 与密码学的关系 费马素性测试通过检查 \( a^{n-1} \equiv 1 \pmod{n} \) 来推测 \( n \) 是素数，但卡迈克尔数会通过所有以 \( a \) 为底的测试（只要 \( \gcd(a, n) = 1 \)），因此费马测试无法检测出卡迈克尔数。 改进 ：更高级的素性测试（如 Miller-Rabin 测试）能有效排除卡迈克尔数。 6. 构造卡迈克尔数的方法 ** Chernick 公式** （1939）：若 \( k \) 使得 \( 6k+1, 12k+1, 18k+1 \) 均为素数，则 \[ n = (6k+1)(12k+1)(18k+1) \] 是卡迈克尔数。 例：\( k=1 \) 得 \( 7 \times 13 \times 19 = 1729 \)（但不是最小，因 \( 561 < 1729 \)）。 7. 推广：Korselt 准则 Korselt 准则 ：合数 \( n \) 是卡迈克尔数当且仅当： \( n \) 无平方因子； 对每个素因子 \( p \mid n \)，有 \( p-1 \mid n-1 \)。 这提供了不依赖具体底 \( a \) 的判别法。 8. 开放问题 是否存在无穷多个三因子的卡迈克尔数？ 卡迈克尔数的精确分布仍未完全解决。