动机
由于剩余类只有有限多个,模整数的重复乘幂最终必然重复。对于单位,消去律把这种重复拉回到 :它的各次幂构成一个从单位元出发的真正循环。这解释了为什么大指数可以化简,也解释了为什么只有在检验互素之后,这种化简才是合理的。
定义
定义 3.1.1
(欧拉(Euler)函数与乘法阶)
对 ,设 为模 的单位组成的集合,并令 。若 ,则阶 是满足 的最小正整数 。
为说明阶的存在性:在 中必有两个幂相等。用较小幂的逆元去乘,就得到一个等于 的正次幂。由良序原理,满足条件的最小指数存在。该假设排除了诸如模 的 这样的数,它的正次幂永远不等于 。
定理/命题
定理 3.1.2
(欧拉定理与费马(Fermat)小定理)
若 且 ,则 。特别地,对素数 且 ,有 。对每个整数 (包括 的倍数),都有 。
定理 3.1.3
(阶刻画所有的返回时刻)
若 ,则对每个非负整数 , 当且仅当 。因此 。更一般地,对正整数 ,
证明思路
证明
(乘以单位是单位集合的置换)
乘以单位 会置换 :它把单位映为单位,其逆映射是乘以 。取代表元 ,其中 。把所有像相乘,得到
单位之积有逆元,所以消去后即得欧拉定理。对于素数 ,每个非零剩余都是单位,因此 。当 时,乘以 即证明对所有整数成立的版本;当 时, 与 模 都为零。
证明
(对指数作带余除法)
关于阶的判别准则,写 ,其中 。于是 ;若它等于 ,由最小性可得 。反方向则对 取幂即可。这一论证也包括 的情形。最后, 恰好当 时成立。令 ,写 ,,且 ,则该条件等价于 。其最小正解为 ,公式得证。
证明透视
带余除法给出逆命题
知道阶本身是返回指数,只证明了它的倍数都会返回。要证明返回指数只有这些,可将任何给定的指数除以阶。余数也会是返回指数。由于它小于最小的正返回指数,只能为零。正是这一逆命题,使后面所有的因数检验与生成元计数成为可能。
这些都是关于单位的精确陈述,并不是说每个阶都等于 。欧拉定理给出的是对所有单位都有效的公共指数;个别循环可以更短。
例题详解
例题 3.1.4
(大指数与小循环)
模 ,有 及 。阶为 ,因为 且 。因此,由于 ,得 。这一计算用的是真实的返回指数,而不是对幂的某种近似。
例题 3.1.5
(通过排除真因数来确定阶)
模 ,由费马定理得 。 的任何真因数都整除 或 。但 ,,二者都不是 。因此 。再由阶的公式,。
例题 3.1.6
(通过费马检验并不能证明是素数)
合数 满足 ,因为 。于是 。它虽是合数,却通过了以 为底的费马条件。在正确使用假设的前提下,检验失败可以证明是合数,但仅凭检验通过并不构成素数的证明。
为什么有限重复只对单位才成为循环
由重复乘法生成的有限个剩余状态序列,最终必然重访某个状态。若不具备可逆性,重复的片段不必包含初始值 。例如,模 时 的各次正整数幂会到达零并停留在零。这个过程有一个短的重复尾段,但从不正向返回到 。把该尾段的长度称为乘法阶,既违背定义,也会使证明中对消去律的每一次使用失效。
对于单位,乘法是全体剩余上的一个置换,并且有逆置换。若两个幂相等,便可以按较小的指数向后退。于是返回从 开始,不可能存在过渡部分。在第一次返回之前,循环中的每个位置都互不相同。这给出了阶的有限状态解释,而且完全保持在代数范围内:关键要素是转移的可逆性。
概念视角结构
阶作为可逆轨道的长度
考察 在乘以某个固定单位下的轨道。该轨道会回到 ,并且恰由第一次返回之前的各次幂构成。把指数按阶化简,就是在这条轨道上选取同一个位置。欧拉定理的指数可能绕轨道若干圈,它不必等于轨道的长度。
欧拉乘法论证用到了什么、没有用到什么
欧拉定理的证明常被压缩为“把简化剩余相乘”。被相乘的集合必须说清楚:它包含每个单位类的一个代表元,而不是每个非零剩余。对于合数模,存在非零的非单位,把它们包括进来会使乘积不可逆。这样一来,消去这一步就没有依据了。证明之所以成立,是因为所选的乘积在每一步都是单位。
无需断言乘以单位后这些代表元的数值或次序保持不变。保持不变的是它们的类所构成的集合。约化之后代表元可以改变,但每个单位类恰好出现一次,因为乘以单位既是单射又是满射。因此,完整代表元列表的乘积彼此同余。这是关于置换的陈述,而不是关于整数的某种方便排序。
也可以把这个证明看作有限群论证的特例。用那种语言来说,单位在乘法下构成群,欧拉指数就是该群的阶数。直接的置换证明的优点是每一步消去都清晰可见,并且不需要事先具备任何群论定理。以后的代数可以更一般地组织同样的推理,但这个初等证明本身已经完整。
在得到指数上界之后高效确定精确的阶
假设已经证明某个指数能使单位回到 。精确的阶必定整除该指数。因此无需检验它以下的每一个正整数。对该指数做因数分解,对每个素因数,检验去掉一个该素因数之后是否仍是返回指数。如果是,就用较小的指数替换当前上界并继续;如果不是,则该素数幂的贡献不能从当前上界中去掉。
这一化简的正确性来自每个返回指数都被阶整除。当某个素因数被成功去掉时,阶仍整除新的上界。若没有任何素因数可以去掉,则不可能还剩下真因数:任何真因数都至少缺少上界的一个素因数,因而整除某个被检验过的较小指数。这与已失败的检验相矛盾。该过程明确了两项责任:先证明一个返回上界,再排除所有更小的因数可能。
对于有许多小因数的指数,这可以显著减少检验次数。但它并不使整数分解变得没有代价,也不是对任意大模数的一般复杂度断言。数学上的结论仅仅是:因数结构可以组织对阶的有限搜索。只要对固定模数始终一致地做约化,就可以用反复平方来完成幂的检验,而无需展开巨大的整数。
幂的阶刻画子循环
在循环中每隔两个、三个或更多个点取一个,可能只访问较少的位置。幂的阶公式恰好度量了访问多少个位置。如果步长与循环长度有公因数,则游走被限制在相对于该因数的某一个同余类的位置中。如果二者互素,则每个位置最终都会被访问。这就是为什么一个生成元的幂本身是生成元,当且仅当其指数与原来的阶互素。
举一个小模型:把十个位置排成一圈。每次移动四个位置,则在返回之前访问五个位置;每次移动三个位置,则访问全部十个位置。两种情形的算术解释相同:第一个正的移动次数必须使步长与移动次数之积被十整除。这里不需要任何几何假设;圆只是把定理中证明的整除条件展示出来。
解读素性检验而不颠倒蕴含
费马定理的逻辑形式是:如果模数是素数且底不被它整除,则某个指定的幂回到 。其逆否命题是:在已核对底的条件的前提下,这种返回的失败可以排除素性。其逆命题会说返回就证明是素数;前面的合数例题驳斥了这一点。这种区分是逻辑问题,与数值精度无关。
对多个底通过检验可以提供更多的证据,但这里所陈述的初等定理并不会把任何未加说明的若干次通过变成证明。严格的证明需要另一条带有自身假设的定理。特别是,找到某一个底的短幂循环,只是描述了该底的阶;它并不决定所有剩余的结构,也不决定模数是否为素数。把这些结论区分开,可以避免要求一次有效的计算去证明它实际上并未确立的内容。
在起点处检验所声称的周期
对单位所提出的指数周期,可以在 处检验:它是周期,恰好当底的这个次幂等于 。如果成立,乘以任意次幂即可看出,把任何指数平移所提出的周期,值保持不变。反过来,对所有非负指数都有效的周期,特别是必须在指数零处保持该值,因此必须回到 。这一等价关系把周期序列的语言直接与阶的定义联系起来。对于非单位,最终周期可能只在一段初始部分之后才成立,模 时 的幂就说明了这一点。因此,检查该序列后段的值,并不能证明可以化简较前的指数。务必说明周期性是从零开始,还是仅在某段过渡部分之后才开始;只有前一种说法才支持用所声称的周期对非负指数进行无限制的化简。
常见错误
常见错误
(底不是单位时化简指数)
按 化简指数需要底是单位。模 时,把指数 化简为 ,会错误地把 与 视为相同。指数同余并不自动意味着任意底的幂同余。
常见错误
(把费马定理倒过来,或假定阶最大)
费马定理的逆命题也不成立, 即是例子。即使模数为素数,阶也不必取到最大:模 ,类 的阶为 ,尽管 。要确立一个阶,既要给出一个返回指数,也要说明为什么没有更小的因数可行。
反例模式
费马定理对所有整数的形式需要素数模
命题:既然 为素数时 对每个整数成立,那么对每个 及每个整数 ,都有 。取 、。则 ,而 ,但 。素数的情形之所以成立,是因为模 唯一的非单位是 ,任何次幂都保持它不变;模 时非单位 不是零,却有 。修正后的叙述是把欧拉定理乘以 ,因此要求 ;没有这个假设时,本节只对素数模保证此同余式对每个整数成立。
总结
欧拉定理来自对单位的置换。带余除法把最小返回指数变成对每个返回都适用的整除判别准则。幂的阶则由整数条件 的化简得出。
练习
快速检查
(求 模 的阶,并计算其立方的阶。)
先得到一个指数上界,再检查它的因数。
解答 · 答案
,,且 。因数 都不回到 ,所以阶为 。 的阶为 ,与 一致。
快速检查
(证明:模 的单位的阶恰为 ,当且仅当它的平方为 而它本身不是 。列出模 的所有这样的单位。)
对于合数模,阶为 的元素不必是剩余 。
解答 · 答案
阶为 ,恰好意味着指数 回到 而指数 不回到。反之,如果这两个条件成立,则最小正返回指数整除 且不是 ,所以是 。模 的单位为 ,它们的平方都是 。因此 恰好是阶为 的单位。
快速检查
(计算 模 的值,并解释为何可以化简指数。)
使用 之前,先检查是否互素。
解答 · 答案
由于 ,欧拉定理给出 ,所以指数可以模 化简。因为 ,得 。事实上 、,所以 ,不能再作更小的化简。