【卡迈克尔数判别准则】在数论中，卡迈克尔数（Carmichael numbers）是一类特殊的合数，它们在某些特定的条件下表现出类似素数的性质。特别是，它们满足费马小定理的条件，但本身并不是素数。因此，卡迈克尔数在密码学和数论研究中具有重要意义。
本文将总结卡迈克尔数的基本定义、判别准则以及相关特性，并通过表格形式清晰展示关键信息。
一、卡迈克尔数的定义
卡迈克尔数是一个大于1的合数 $ n $，满足以下条件：
对于所有与 $ n $ 互质的整数 $ a $，都有
$$
a^{n-1} \equiv 1 \pmod{n}
$$
换句话说，卡迈克尔数在费马小定理的测试中会“通过”，尽管它不是素数。
二、卡迈克尔数的判别准则
根据Korselt于1899年提出的判别准则，一个正整数 $ n $ 是卡迈克尔数当且仅当满足以下三个条件：
| 条件 | 内容 |
| 1 | $ n $ 是合数 |
| 2 | $ n $ 没有平方因子（即 $ n $ 是无平方因子数） |
| 3 | 对于每个素因数 $ p $，都有 $ p - 1 $ 整除 $ n - 1 $ |
三、卡迈克尔数的性质
1. 最小的卡迈克尔数是561，它是 $ 3 \times 11 \times 17 $ 的乘积。
2. 卡迈克尔数的数量是无限的。
3. 所有卡迈克尔数都是奇数。
4. 卡迈克尔数不一定是素数幂次，而是多个不同素数的乘积。
5. 卡迈克尔数在密码学中可能被用于伪造素数检测。
四、典型例子
| 数字 | 是否为卡迈克尔数 | 原因 |
| 561 | 是 | $ 561 = 3 \times 11 \times 17 $，且 $ 3-1=2 $、$ 11-1=10 $、$ 17-1=16 $ 都能整除 $ 560 $ |
| 1105 | 是 | $ 1105 = 5 \times 13 \times 17 $，且 $ 5-1=4 $、$ 13-1=12 $、$ 17-1=16 $ 都能整除 $ 1104 $ |
| 1729 | 是 | $ 1729 = 7 \times 13 \times 19 $，且 $ 7-1=6 $、$ 13-1=12 $、$ 19-1=18 $ 都能整除 $ 1728 $ |
| 123 | 否 | 不满足无平方因子或 $ p-1 $ 整除 $ n-1 $ 条件 |
五、总结
卡迈克尔数是一种特殊的合数，其在费马小定理下表现得像素数。判断一个数是否为卡迈克尔数，需同时满足三个条件：合数、无平方因子、且每个素因数减一都能整除该数减一。这些性质使得卡迈克尔数在理论和应用上都具有重要价值。
通过理解这些规则，我们可以更准确地识别和处理这类数，在密码学、算法设计等领域中避免误判。