动机
为什么要超越欧拉定理?
欧拉(Euler)定理说,只要 ,就有 。指数 总是可用,但往往远大于对所有单位同时成立的最小指数。模 的单位为 ,它们的平方都是 ;尽管 ,指数 已经足够。我们还会看到,模 的每个单位都满足 ,但 。
于是自然要问:使每个单位都满足 的最小正整数 是多少?答案是 Carmichael 函数 。它还可用于研究另一个问题:费马(Fermat)小定理说明素数 对每个与 互素的底数满足 ;哪些合数 对每个与 互素的底数都满足 ?了解 后,Korselt 判据将给出答案。
以下均设 。记 为模 与 互素的剩余类构成的乘法群,故 。对单位 , 是它在 中的阶。我们使用有限群的基本事实: 当且仅当 。
通用指数
定义 3.2.1
(通用指数与 Carmichael 函数)
设 。若正整数 满足
则称 为模 的通用指数。由欧拉定理, 是通用指数,故这样的指数存在。Carmichael 函数 是其中最小的正整数。
定理 3.2.2
(通用指数的结构)
设 是 遍历 时所有 的最小公倍数,则:
- 正整数 为通用指数当且仅当 ;
- ;
- 为通用指数当且仅当 ;特别地,。
证明
(阶与它们的最小公倍数)
是通用指数当且仅当每个单位 均满足 ,亦即每个 。有限个正整数都整除 ,当且仅当它们的最小公倍数 整除 ,得到 (1)。因此通用指数恰是 的正倍数,其最小值为 ,得到 (2),并由此得到 (3)。欧拉定理使 成为通用指数,故 。
这里关键是整除性:仅凭最小性只能得到 。结构定理还说明每个对所有单位有效的指数都是最小指数的倍数。
只讨论单位。 定义仅量化单位,不能推广到非单位。若 ,则任何 都不可能满足 :否则 同时整除 和 ,便会整除 。例如 只会是 或 ,从不是 。
用中国剩余定理分解模数
定理 3.2.3
(最小公倍数公式)
若 且 ,则
因此若 ,其中 两两不同,则
证明
(互素因子的通用指数)
写 。我们证明 是模 的通用指数,当且仅当它同时是模 的通用指数。
先设 对模 通用,任取模 的单位 。中国剩余定理给出整数 ,使
于是 分别与 互素,故与 互素。由 ,模 约化得 。对 同理。
反之,若 对两个模数都通用,且 ,则 都整除 。它们互素,所以乘积 也整除 。
由结构定理,这些通用指数恰是同时被 整除的正整数,其最小值为两者最小公倍数。对素数幂个数 归纳即可得到一般公式:各素数幂两两互素,最小公倍数满足结合律。
计算因而归结为素数幂。奇素数幂与 的幂表现不同,必须分开处理。
奇素数幂
定理 3.2.4
(奇素数幂)
若 为奇素数,,则 。
证明
(生成元的阶为 )
使用先前建立的奇素数幂原根定理: 是循环群。取生成元 ,则 。结构定理表明 是每个单位的阶的倍数,故 ;结构定理还给出反向整除,因此二者相等。
特别地, 给出 。
2 的幂
定理 3.2.5
(2 的幂)
证明
(以平方得上界,以单位 得下界)
小指数情形。 ,故 。,且 、,故 ,。
的上界。 对 归纳,证明每个奇数 都满足
当 ,写 ,则 ; 为偶数,故 。若 ,平方得
因为 ,右边模 同余于 ,即为 的结论。所以 是模 的通用指数,结构定理给出 。
的精确阶。 我们证明每个 都有
亦即 ;这里 是素因数分解中 的指数。 时 。若结论对 成立,则二项式定理给出
括号内是奇数加偶数,仍为奇数,归纳完成。
固定 。由上界, 整除 ,故为某个 ,。若 ,则 ,即 。但上面的结论取 给出赋值恰为 ,矛盾。因此 。
是 的阶的倍数,又整除 ,故两者相等。
证明透视
2 的幂的论证结构
- 上界: 平方把误差项 变为 ,因此模数翻倍时所用指数也翻倍。
- 下界: 一个具有足够大阶的具体单位就足够; 是直接由二项式定理证明的,没有调用未说明的提升引理。
- 为何要求 : 基础情形使用 。 时公式给出 ,但 ; 时公式甚至不是整数。
与 的差距在 时已经出现。
反例模式
$\lambda(8)$ 严格小于 $\varphi(8)$
模 , 的平方分别为 ,都同余于 。由于 ,指数 无效,故 ,但 。
因此模 没有阶为 的单位, 不是循环群。更一般地,对 ,,所以模 没有原根;奇素数幂的原根定理不能直接用于这些模数。
指数 对非单位并不适用:模 ,、、。
例题 3.2.6
(计算 )
。由最小公倍数公式及两条素数幂定理,
而 。因此每个模 的单位满足 。抽查:,。 整除 ,商为 。
概念视角结构
Carmichael 函数是群的指数
用群的语言说, 是有限阿贝尔(Abel)群 的指数,即其所有元素阶的最小公倍数。在阿贝尔群中,这个最小公倍数总能取到:若可交换的两个元素的阶 互素,它们的积的阶就是 ;对每个素数,取阶中含该素数最高幂的元素并把它们组合,便得到一个阶恰为 的单位。所以 是循环群,当且仅当 ; 时这不成立。
Carmichael 数
定义 3.2.7
(Carmichael 数)
Carmichael 数是满足下列条件的合数 :对每个满足 的整数 ,
由结构定理,定义条件恰好说 是模 的通用指数。因此合数 是 Carmichael 数当且仅当 。
边界情形。 定义排除素数。例如 依费马小定理对每个单位满足同余,但它不是合数。最小合数 不满足:;具体地,。
定理 3.2.8
(Korselt 判据)
合数 是 Carmichael 数,当且仅当:
- 无平方因子;
- 对每个整除 的素数 ,有 。
证明
(以两个见证元证明必要性,以最小公倍数公式证明充分性)
必要性:无平方因子。 设 为 Carmichael 数,假设某个素数 满足 。写 ,其中 、。由中国剩余定理取 满足
若 ,取 。由于 且 ,有 ,因而 。
由 ,在模 下有 。对 ,二项式定理给出
取 ,得到 ,所以 。但 ,于是 ,矛盾。该论证对 也成立。
必要性:整除条件。 设 ,写 ,其中 。若 ,则 整除任何整数;故设 为奇数。由原根定理 的情形,存在模 的原根 ,即 。因 ,它也是模 的单位。由中国剩余定理取
于是 ,故 。模 约化得 ,因此 。
充分性。 设合数 无平方因子,写为不同素数之积 ,且每个 。奇素数幂定理给出奇素数的 ,2 的幂定理给出 。由最小公倍数公式,
每个 都整除 ,故其最小公倍数也整除 。于是 , 是通用指数, 是 Carmichael 数。
证明透视
各假设如何出现
- 无平方因子: 单位 的幂模 形如 。若指数 使它同余于 ,便要求 ,这与 矛盾。
- : 模 的原根的阶恰为 ;中国剩余定理将它嵌入模 的单位,同时控制其他素因子。
- 充分性: 无平方因子时, 是各 的最小公倍数;假设恰好要求这些数都整除 。
例题 3.2.9
(561 是 Carmichael 数)
是无平方因子的合数,。逐一检查:
由 Korselt 判据, 是 Carmichael 数。也可计算 ,且 。
欧拉定理本身不能解释这个结论: 不整除 ;整除 的是较小的指数 。
例题 3.2.10
(341 通过底数 2,却不是 Carmichael 数)
无平方因子。由于 ,有 ,底数 不能检出 为合数。
然而 ,故 。由 Korselt 判据必有某个单位不通过;取 :
- 模 :,且 ,故 。
- 模 :费马定理给出 ,故 。又 ,,因此 。
所以 。
反例模式
无平方因子并不足够:$n=15$
是无平方因子的合数,但 ,因此不是 Carmichael 数。这里 。
证明中的方法可构造反例: 是模 的原根,解 和 得 。由于 、,有 。
某些底数仍能通过。每个单位满足 ,所以 ;恰好满足 的单位通过,即 ,它们是八个单位中的四个。
一个底数与所有底数
对与 互素的单个底数 ,费马检验询问 是否成立。不成立就由费马小定理证明 为合数;成立本身不能证明素性: 通过底数 , 通过底数 。通过某个底数的合数不一定是 Carmichael 数。
Carmichael 条件涉及每个单位,等价于单一整除式 。按定义直接验证需要检查 个剩余类;Korselt 判据把它换成每个素因子一次整除检查,但前提是已知 的分解,因此它是结构刻画,不是识别素数的捷径。
与 有公共因子的底数不在定义范围内。特别地,,因为 而 。
常见误解
- “最小仅仅意味着数值最小。” 结构定理更强:每个通用指数都是 的倍数。
- “无平方因子的合数都是 Carmichael 数。” 是反例,整除条件不可少。
- “通过一个费马底数就意味着是 Carmichael 数或素数。” 是反例。
常见错误
(以为 )
这对奇素数幂以及 成立,但对 等不成立。
常见错误
(对小的 套用 )
公式要求 ;小指数的正确值是 、。
常见错误
(把通用指数用于非单位)
它只适用于单位;非单位的任何正整数次幂都不可能同余于 。
练习
快速检查
(计算 ,并与 比较。)
解答
。由最小公倍数公式及两条素数幂定理,
另一方面,。
快速检查
(证明对每个 , 都是偶数。 时如何?)
解答 · 答案
设 。因为 ,;而 ,所以 。由结构定理,。当 , 且 为奇数,所以 的假设必要。
快速检查
(证明 是 Carmichael 数,并计算 。)
解答 · 答案
是无平方因子的合数,且 。因此 均整除 ,Korselt 判据适用。又 ,且 。
快速检查
(证明每个 Carmichael 数都是奇数,且至少有三个不同的素因子。)
解答
设 是 Carmichael 数,由判据知它无平方因子。
奇性。 若 ,由于 是无平方因子的合数,必有另一个奇素因子 。则偶数 整除奇数 ,矛盾。
至少三个素因子。 无平方因子的合数至少有两个不同素因子。若 ,其中素数 ,则
由 得 ,但 ,矛盾。故 至少有三个不同素因子,且均为奇数。
快速检查
(设 是 Carmichael 数,证明对每个整数 ,包括非单位,都有 。)
解答
任取整除 的素数 。若 ,则 模 均为零。若 ,费马小定理给出 ;由 Korselt 判据 ,故 ,进而 。
因此 的每个素因子都整除 。由于 无平方因子,是这些两两互素素数的乘积,故 。
例如 、 时,,尽管 。同余式 对所有 成立; 只保证对单位成立。