动机
每个素数模数都有原根,但合数模数可能把几种不同的周期来源结合起来。完整分类既需构造,也需障碍。构造须证生成元的阶在每个更高素数幂中,都取得应有的新素因子;障碍则须解释,为何几个各自循环的部分,经中国剩余重建后未必合成一个完整循环。
本篇证明:对每个整数 ,存在原根当且仅当 是二、四、奇素数幂或其两倍。前篇的素数模原根定理是明确使用的起点;另用已证的阶整除判据、Euler 定理、整数素分解及中国剩余定理。不假设任何额外的原根存在定理。
论证区分模素数的剩余类与其整数代表元。这些代表元到了素数平方会成为不同的类,而差别可能决定阶是否增大。构造中加上一个素数的修正,正是来自这个小而重要的区分。
定义
定义 5.2.1
(单位、原根与赋值)
记 为单位类的乘法群,具有 个元素。模 原根是阶等于 的单位,等价地是 的生成元。平凡群也循环,所以模二的唯一单位一就是原根。
对素数 及非零整数 ,以 表示使 的最大整数 。凡使用有限赋值的命题均排除 。
模 恰有 个单位,因为被排除的恰是 的倍数。单位的每个返回指数都被其阶整除,阶又整除单位群大小。这些限制可能的阶,却还未证明最大可能阶会出现。
若 互素,中国剩余映射给群同构 。环映射双射且保持乘法,一对单位坐标有逐坐标逆元,其原像亦可逆;反之单位必映到单位。这验证单位群命题,而不只是比较两边数目。
定理 / 命题
定理 5.2.2
(选出能生成全部奇素数幂的提升)
设 奇,正整数 模 为原根。 与 至少一个是模 原根。任何模 原根整数 ,对每个 也都是模 原根。
定理 5.2.3
(所有至少二的模数之完整分类)
对 , 循环当且仅当
其中 为奇素数、。所以恰好这些模数具有原根。
证明思路或证明
先确保素数平方的阶
证明
(一次修正确保素数平方)
化简到模 ,知 模 的阶是 的倍数;它又整除 ,故只能是 或 。因此 模 为原根,恰在 时成立。
若此条件成立,取 。若不成立,展开另一提升:
其余项均含 。系数 模 非零,因 可逆且 。所以第一个幂模 为一时,第二个就不为一。新提升模 仍为 ,相同的阶论证使 在模 为原根。这证明最初的存在步骤,无需搜索平方模数的全部单位。
一步二项展开控制精确赋值
证明
(精确赋值增长给出完整的阶)
对奇 ,设有限 ,写 ,其中 。要证
二项展开首项为 。对 ,第 项因 ,赋值至少 。最后一项赋值为 ,用到了 。因此
首系数仍模 可逆,所以赋值恰为 ,而不只是至少如此。正是这个精确性,排除阶增长不足的情况。
化简 满射,因每个非零素数层剩余类都能提升成单位;所以生成元也化简成生成元。若 为模 原根,则 模 为一、模 却不为一,因此其与一之差赋值为一。反复用二项步骤,得
令 为 模 的阶。模 化简给 ,Euler 给 ,所以 ,其中 。赋值式说此幂模 返回一,恰在 时成立,故 ,阶正是 。同一整数 适用于每个 。
证明透视
返回幂不等于精确阶证书
三个事实确定 模 的阶 ,每个排除一种不同的损失。由于 模 约化为生成元,其阶是 的倍数。欧拉(Euler)定理给出 ,所以 ,其中 。关键一步是精确赋值 :若只有不等式 ,只能说明某个幂回到 ;等式则说明对每个 都有 。
为奇数只在一处用到,即二项展开的最后一项:只有当 时, 的赋值才至少为 。对 与 ,这一步失效,因为 而不是 。起始情形 正是第一步所确保的平方层原根性。
构造允许的偶模数
证明
(偶模数的存在性)
模 、模 的单位群直接可见是循环群,生成元分别为 、。奇 时,前面定理由素数层生成元构造每个 的原根。
由 平凡,CRT 给 。所以模 的生成元,有唯一奇数提升到模 ,且阶不变。给定代表元 ,奇时取 ,偶时取 。奇偶检查不可省,偶代表元根本不是加倍模数的单位。至此每个列出类型均已证存在。
过多的一之平方根阻止单一循环
证明
(四个一的平方根与必要性)
在 阶有限循环群,把元素写成生成元幂,则 等价于 ,只有 个解。因此若单位群有四个不同的一之平方根,就不可能循环。
当 ,模 的四类
互异且均为单位,平方皆一。展开 得 ,后两项模 消失。互异使用 ;模 时候选类两两重合。所以 时 没有原根。
每个奇素数幂单位群都有互异的一、负一两根。若模数有两个不同奇素因子,便在这两个 CRT 坐标独立选正负号,其余坐标取一,得到四个互异、平方为一的重建单位。模数同时有四因子及奇素因子时,也可如此,因模四坐标同样有不同的正负号。若二幂坐标更高,它本身已有四根,可配上其余坐标的一。这些单位群都不循环。
为确认没有漏掉模数,写 ,各 为不同奇素数,。若 ,由 知 ,只余 ;若 ,只余 ;若 ,独立奇数坐标的符号已排除循环。留下的恰是定理类型。这完成必要方向,而非只给几个失败例子。
证明透视
一个不变量排除所有被排除的模数
必要性证明只用一个不变量: 的解的个数。在循环群中它至多是二,因为 有 个解;这是循环性唯一出场之处。其余部分都在制造四个解。对 的 ,四个解可以明确写出,而假设 正是使 与 不同的条件。其他情形由 CRT 推动:两个各自含有相异符号 的坐标给出独立的选择。最后的分解计数说明,这两种机制覆盖了列表以外的每个模数。
例题详解
例题 5.2.4
(素数层生成元可能有错误提升)
整数 模 的类为 ,所以是原根。但 ,其模 的阶只有 ,而非 。改成 ,有 ,赋值为 。所以 对每个 都是原根。模 时其阶为 ;其六次幂为 ,所以较小的候选指数 并不足够。修正把同一素数层代表元,改成平方层真正不同的类。
例题 5.2.5
(奇数提升给模五十生成元)
由于 , 是模 的原根,且 。因此 生成模 的单位,但它是偶数,不是模 的单位。所需的奇提升为 ,阶仍为 。直接验证 、,排除 的极大真因数 与 ,给出独立的精确阶证书。模 共有 个原根,由此生成元的互素指数幂得到。
例题 5.2.6
(循环坐标未必给循环直积)
的局部单位群都是循环群,阶分别为 与 。但模 时 的平方都是 ,故全局群不循环。两坐标的生成候选同时返回,由最小公倍数而非乘积控制。特别地, 模 的阶为 ,而 。很长的幂循环,未必就是完整循环。
概念视角结构
CRT 同步不同的返回时间
直积元素的分量阶为 时,其阶为 ,因恰在两个分量阶都整除指数时返回。对阶为 的循环因子,每个分量阶都整除因子阶,故直积元素阶都整除 ,而一对生成元达到此界。因此直积循环当且仅当 。两个奇素数幂单位群的阶均偶,循环共享因子二,不能合成与直积大小同长的循环。CRT 保持乘法,并未说独立循环的长度互素。
常见错误
反例模式
原根的提升不一定是平方模的原根
一个看似合理的说法是:模奇素数 为原根的整数,模 也仍是原根。模 时整数 是原根, 也是。但 ,故 ,而 。因此 , 的阶为 ,不是 。相反,,所以 本身是模 的原根。正确的说法是提升定理: 与 至少有一个可行;而一旦模 的阶达到最大,所有更高的幂都随之成立,无须另选生成元。
常见错误
(以为局部循环便给出循环直积)
每个 CRT 坐标的单位群都循环并不足够,只要两个坐标的阶有公因数。模 时, 与 分别是阶 与 的循环群,但每个单位都满足 ,所以没有单位的阶为 。
常见错误
(把域上的根数界搬到合数模)
“二次多项式至多有两个根”只在域上成立。模 时, 的四个根 确实存在;它们矛盾的是循环性,而不是多项式的界。检查阶或计算生成元时,也要分清取值模数 与指数模数 。
总结
加上一个素数的修正,确保奇素数平方的原根;精确赋值增长再证每个高幂都有最大阶。CRT 把生成元转到两倍模数,四个独立的一之平方根则排除其余全部类型,完成 分类的两个方向。
练习
快速检查
(固定奇素数 的正原根 。证模 的 个提升 中,恰一个不是原根;解释只查 为何总能成功。)
解答 · 答案
由 Fermat 写 。二项式给 。 的系数模 可逆,恰一 使括号零;恰该提升阶为 ,其余阶为 。若 失败, 成功;若已成功,无须修正。保证的是两者至少一个,不是两者总都是原根。
快速检查
(从 模 开始构造模 的原根,并给出直接的阶证书。)
解答 · 答案
由于 的赋值为 , 是模 的原根;它到模 的奇提升为 。计得 、。阶整除 ,却不整除 或 ,故恰为 。这两者是 的极大真因数 与 ,因而排除全部较小因数。
快速检查
( 中哪些有原根?对每个允许者给一生成元,并以构造或前例说明。)
解答 · 答案
恰 符合,生成元依次为 。 生成模 的单位且本身是奇数,故适用于模 ; 因 而生成模 的单位,且本身是奇数,故适用于模 ;由赋值检验, 适用于 与 的各次幂; 已在模 证明。其余模数具有禁止的二幂因子,或至少两个不同奇素因子,正是分类排除的情形。
快速检查
(解释赋值步骤为何不能直接套到 。用 计算,并联系原根由 提升到 的失败。)
解答 · 答案
,但 ,不是 。二项证明在 时,最后项赋值未必至少 ,可与首项互相影响。 生成模 的单位,模 时阶却只有 ,而非所需的 。这是真正的群结构障碍,四个一之平方根也可证明,不只是奇素数证明存在缺口。