动机
欧拉(Euler)定理给出了每个单位的循环周期的上界,但并不保证存在一个包含所有单位的循环。原根恰好提供这一点:每个单位都成为某个选定剩余类的幂。于是乘法变为指数的加法,看似非线性的幂方程化为线性同余。存在性证明依赖于素数模的一个特征,而合数模可能不具备该特征:域上多项式的根的个数上界。
定义
定义 5.1.1
(原根与离散对数)
模 的原根是满足 的单位 。此时它的幂 恰好是全部单位,且无重复。相对于 ,单位 的离散对数是模 的唯一指数类 ,满足 。
离散对数是一个指数的剩余类;选取其中一个整数代表元则是进一步的约定。其定义并不断言它容易计算。这里的小型表格只是用来说明代数结构,而不是暗示存在一般的高效算法。
定理/命题
定理 5.1.2
(素数模的原根)
对每个素数 ,模 的单位群存在原根,且恰有 个原根。素数 也包括在内:它唯一的单位 的阶为 ,而 。
定理 5.1.3
(在循环单位群中解幂方程)
设 是模 的原根,令 ,并把单位写成 。对正整数 ,方程 的单位解通过 与 的解一一对应。因此,除非 ,否则没有单位解;若此条件成立,则恰有 个解。
证明思路
证明
(以互素的阶合并各素数幂部分)
首先,域上 次非零多项式至多有 个根。若 是一个根,多项式除法给出因式 ;由于域中没有零因子,对次数作归纳即可约束其余的根。这适用于模素数的剩余类。
设 为奇素数,并写 。对每个满足 的素数 ,多项式 的根少于 个,因此可选取非零剩余类 使 。设其阶为 。由欧拉定理得 。因为 ,所以 中 的指数恰为 。因此
由幂的阶公式,其阶为 。
阶互素(分别为 )的可交换元素,其乘积的阶为 。事实上,若 ,则 同时属于两个循环子群。它的阶同时整除 ,故为 。于是 且 ,从而 ;而指数 确实成立。反复运用这一事实,可知 的阶为 。这就证明了存在性。
每个单位都是 的形式。其阶为 ,所以它是原根当且仅当 。这样的指数类共有 个。
证明
(指数坐标把幂方程化为线性同余)
写 、。由阶的判别准则, 等价于 ,再由线性同余定理得到解的个数。特殊的指数模 只有一个类,结论直接成立。
证明透视
域与互素的阶分别在哪里用到
域只用到一次:根的上界保证次数为 的 不可能在全部 个非零剩余类上都为零。由此得到元素 ,其阶 整除 但不整除 ,所以 含有完整的幂 。被选元素不必是生成元;幂 去掉不需要的因子,其阶恰为 。
关键一步是互素阶引理,它需要两个假设。可交换性使 能拆分为幂的乘积,而互素的阶使两个循环子群只在 处相交。在单位群中,两者都由构造保证,而这些素数幂阶相乘正好是 。模 时根的上界失效,因为 有四个根,而确实没有任何单位的阶为 。
例题详解
例题 5.1.4
(模 7 的完整幂表)
模 下, 依次为 。由于六个单位全部出现, 是原根。原根对应的指数与 互素,即 ,所以原根是 和 。特别地,阶最大并不意味着数值最大的剩余类。
例题 5.1.5
(从三次方程到线性同余)
解 。由表知 ,令 ,解 。解为 ,得 。它们的立方的余数都是 。非单位不可能是方程的解,因为它的立方不是单位。
例题 5.1.6
(素数模与合数模的表现不同)
模 时,单位 的平方都是 ,所以没有单位的阶为 ;不存在原根。此外 模 有四个根,超过其次数。这并不与多项式根的个数上界矛盾,因为该上界的域假设不成立。相反, 模 的阶是 :由模 的约化知其阶被 整除,又整除 ,故为 或 ;而 排除了 。
生成元对欧拉定理增添了什么
欧拉定理告诉我们,每个单位在一个共同的指数处回到一。它并没有说单个单位的幂能到达其他单位。原根增添了一个完整的坐标系:每个单位被赋予一个指数类,乘法对应于坐标的加法。这是比周期性更强的结构性论断,需要单独证明。
这一区别在模八时清晰可见。每个单位都有短循环,但没有一个循环长到包含全部四个单位。分开的两元素循环不能仅靠选取更方便的代表元而连接起来。更换代表元不会改变剩余类及其阶。因此,循环性的失败是乘法结构的性质,而不是所选记号的问题。
为什么多项式论证需要域
根的个数的证明反复提取一个线性因子,并论证其他每个根必为剩余因式的根。这一推导用到了没有零因子。在域上,若乘积为零且一个因子非零,则另一个因子必为零。在合数模的剩余类环中,两个非零因子的乘积可以为零。因此,在域上安全的次数上界可能失效。
在存在性证明中,所选多项式的次数严格小于域的非零元素个数。因此它不可能在所有非零元素处都为零。所选元素并不被声称立即就是生成元,它只贡献所需阶中一个完整的素数幂部分。这是核心的策略:分别解决若干较小的阶的要求,再利用互素性把它们合并。
反例模式
乘积的阶不一定是阶的乘积
一个诱人的捷径是:把阶为 与 的任意两个单位相乘,便期望得到阶 。模 时,单位 与 的阶都是 ,因为 且 。它们的乘积是 ,阶为 ,而不是 。这里 与 生成同一个子群,所以相交论证失效。若阶互素,结论便成立: 的阶为 , 的阶为 ,而 的阶为 ,所以 是模 的原根,与幂表一致。
不必列出每个循环即可计数生成元
一旦知道一个生成元,阶公式就一次性刻画了其他所有生成元。与群的大小互素的指数保持完整的循环,而有公因子的指数只访问较短的子循环。这把生成元的计数化为对互素指数类的计数。答案取决于群的大小,而与具体选取了哪个生成元无关。
这一计数并不循环论证。生成元的存在性先由多项式构造证明。之后我们才用它的幂来枚举所有单位,并计数那些具有最大阶的单位。若一开始就把每个单位写成某个未指定生成元的幂,就等于假定了主定理。把存在性与枚举两个阶段分开,是代数证明中一个有用的普遍习惯。
一个小素数可以使这一区别更清楚。知道某个候选元在完整指数处的幂等于一,仅仅是欧拉条件。要证明它是生成元,必须排除该指数的每个真因数作为回归时间。仅检验候选元不是一,只排除了阶为一的情形,而其他所有真阶都未排除。前面的因数检验方法提供了一个简短而完整的证明凭据。
快速检查
(只计算两个幂,证明 是模 的原根。)
须排除的 的真因数,都整除 或 。
解答 · 答案
的阶整除 。若它是真因数,便会整除 或 。但 ,,两者都不是 。因此阶为 , 是原根。
变换坐标后解方程
从指数类到单位的映射是双射。因此,在指数坐标中解方程既不会产生多余的单位解,也不会漏掉有效解。指数的线性同余可能有多个解;由于坐标映射是单射,这些解给出互不相同的单位。这就是线性同余解的个数可以直接转移到原幂方程的原因。
可解性条件用到了目标元的对数,但不依赖于选来代表该对数的具体整数。任意两个代表元相差群的大小,而群的大小被条件中出现的最大公因数整除。因此更换代表元不改变该最大公因数是否整除目标指数。这是一个小小的良定义检验,凡涉及指数类的陈述都应伴随这一检验。
更换原根也不改变解的个数。任何新的原根都是旧原根的一个互素次幂,所以更换坐标相当于把指数乘以一个模群大小的单位。线性同余被双射地映为相应的新同余。数值上的对数改变了,但原方程及其解集不变。
概念视角结构
幂方程化为像与纤维的问题
在指数坐标中,把单位取固定次幂就是把其指数乘以一个固定整数。它与循环长度的最大公因数同时度量了核的大小(即给定次幂为一的单位个数),以及任何可达目标的原像个数。像之外的目标没有原像。这与系数为非单位的线性同余中已见的结构相同。
作为第一个推论的二次剩余
对奇素数,取一个原根并考虑单位的平方。指数循环的长度为偶数。因此平方数的指数为偶数,而每个偶指数都可通过把某个指数加倍得到。恰有一半的非零剩余类是平方数。每个这样的剩余类在单位中有两个平方根,对应于加倍指数同余的两个解。它们互为相反数,因为在奇特征下非零的根不可能等于其相反数。
这一结论是引入二次剩余的有用开端,但它并未证明二次互反律,也没有给出一般的高效平方根算法。生成元表可以解决小的例子,而大的情形则需要额外的计算思想。应当区分可能解的代数分类与求出其坐标的难度。离散对数由唯一性来定义;其计算代价是另一个问题。
当前论证的边界
素数幂的例子表明某些合数模确实有原根。模八的例子表明有些则没有。两者合起来防止了两种错误的推广,但并未建立完整的分类。完整的处理需要考察从奇素数提升到其幂,以及与因数二的相互作用,然后证明相应的必要性命题。这些主题不在本页已完成的证明范围之内。
这一边界是数学上的,而不仅仅是行政上的。多项式根的论证在域上有效,所以不能不加修改地在每个合数模剩余类环上重复。任何推广都必须用新的推理来取代缺失的假设。认识到一个证明在何处失效,往往是通向下一个正确定理的第一步。
常见错误
常见错误
(只检查完整指数而不检查每个真因数)
满足 及 的单位 不一定是原根:欧拉定理对每个单位都给出第二个条件。模 时,单位 满足 ,但早已有 ,所以其阶为 。原根要求对每个素数 都有 。对合数模,原根根本不一定存在,而上面的证明只涵盖素数模。
常见错误
(把指数模 约化而不是模 )
指数坐标以 为模,而数值以 为模。对 及 ,正确的同余式是 ,有三个解 。若改为模 ,得到 ,只有 ,于是遗漏了解 与 。解的个数也只针对单位目标与单位解;零目标需要另行做整除性分析。
总结
域上根的上界产生具有每个所需素数幂阶的元素。它们的互素阶之积生成模素数的全部非零剩余类。一旦固定了生成元,幂方程就化为关于指数类的线性同余。
练习
快速检查
(利用模 的原根 ,列出模 的所有原根。使用阶公式,而不要重新计算每个幂的循环。)
解答 · 答案
与 互素的指数是 。它们对应的 的幂模 分别为 。这恰好是 个原根,因为每个的阶都是 ,且每个单位都是 的幂。
快速检查
(解 ,并证明 无解。使用 的幂表。)
解答 · 答案
由于 ,第一个方程为 ,解为模 的 。因此 模 。对目标 ,方程为 ,由于 ,无解。剩余类 不是任一单位目标方程的解,所以这些结论穷尽了所有剩余类。