动机
问指定剩余是否在平方映射的像内。原根把它化为指数同余,但计算离散对数可能是多余工作。二次互反律改为比较不同素数模数;配合几条初等补充规则,能把许多剩余问题缩成更小者。
论证有几个阶段:先以两种符号辨认非零剩余,再从带符号代表元的有限置换找出符号,最后用两种方式计算同一格点矩形。这会解释互反的负号,而不是只要求记住两素数模四余三时的例外。
主要论证的素数均为奇数。前篇已证域的根数上界、素数模数的 Fermat 定理及基本同余运算。不能把素数换成奇整数,便暗中宣称已得到所有合数模数的结果。
定义
定义 6.1.1
(二次剩余与 Legendre 符号)
对奇素数 ,非零剩余 若可写为 、,称为二次剩余;否则称为二次非剩余。定义
Legendre 符号只依赖分子的模 类。它不是分数,没有已证符号恒等式时,类似分数约消的操作没有意义。
非零平方恰有 类。非零类的平方映射恰把 成对识别: 给域中的 ,故 或 ;奇特征使两者互异。这个初等计数是下面 Euler 准则的起点。
概念视角代数
符号即离散对数的奇偶性
若 是模 的原根, 且 ,则
指数是模偶数 来读的,所以 的奇偶性有明确定义。偶指数显然给出平方;反过来, 给出 ,指数为偶。从这个角度看,符号就是从循环单位群到 的唯一满同态,而对分子的乘法性立即可见。
定理 / 命题
定理 6.1.2
(Euler 判别准则与 Gauss 引理)
若 ,则
令 。对 ,以 表示 的最小正模 代表元,以 计算其中 的数目。则
定理 6.1.3
(二次互反律及补充律)
对不同奇素数 ,
对每个奇素数 ,
两个互反符号恰在两素数都模四余三时相反,其他情况相同。
证明思路
证明
(以平方数计数证明 Euler 准则)
令 。每个非零平方 由 Fermat 满足 模 。这些类恰有 个,而域上的 至多有 根,所以非平方不可能满足此式。任意单位又由 Fermat 得 ,分解平方差知 只能为一或负一。非平方只可能为负一,证明 Euler 准则。
由此符号对分子具乘法性。对单位 ,Euler 准则使 等于对应两符号的乘积。模奇素数时一与负一不同,所以整数符号相同。若某分子被 整除,乘法式两边均零,故规则适用于全部整数分子,也证明后续可分解分子来计算。
带符号置换证明 Gauss 引理
证明
( 的带符号置换)
若 ,取 ;若 ,取 。这些代表元在 内,绝对值互异:若相同,则 ,故 。索引在一至 ,正号迫使相等,负号由 排除。因此绝对值恰排列 。
把带符号代表元相乘,一方面乘积同余于 ,另一方面恰等于 。 的全部因子均不被 整除,所以可合法消去,再用 Euler 准则即得符号公式。证明需要的是绝对值的置换,而非声称正剩余本身就是 。
补充律
证明
(对 与 计算越界次数)
对 ,最小正代表元为 ,全大于 。Gauss 计数 给第一律。对 ,代表元就是未回卷的整数 ,其中恰有
个超过 。当 模八依次余 ,此数奇偶依次为 ;整数 的奇偶亦相同。因此 Gauss 引理证第二律,涵盖每个奇素数类。二由补充论证处理,不是套用要求两奇素数的互反公式。
把符号化为下取整和
证明
(把 Gauss 计数写成下取整和)
需要一个奇偶恒等式。令正奇整数 与 互素,写
并令 为 Gauss 引理中的绝对代表元,其和为 。把负的 换回正剩余 ,得到
模二即 。另一方面, 均奇,把除法等式相加得 。比较得 ,故
奇偶论证使用了 的奇性。忽略假设而用于任意偶分子,便会失去刚刚追踪的符号信息。
下面的互动图对任意奇素数 及分子 ,数出 大于 的剩余个数,把 Gauss 符号与 Euler 判别准则及逐一列出的平方数比较,并显示下取整公式在 为偶数时何处失效。
Gauss 符号计数、Euler 判别准则与逐一检验得到相同结论
选取奇素数 p 及分子 a(p ∤ a)。数出 a·i(1 ≤ i ≤ (p−1)/2)的最小正剩余中大于 p/2 的个数,并把所得符号与 a^((p−1)/2) mod p 及直接寻找平方数的结果比较。
| i | a·i | r_i = a·i mod p | r_i > p/2? | 带符号代表元 t_i | ⌊a·i/p⌋ |
|---|---|---|---|---|---|
| 1 | 3 | 3 | 否 | 3 | 0 |
| 2 | 6 | 6 | 是 | -1 | 0 |
| 3 | 9 | 2 | 否 | 2 | 1 |
带符号代表元的绝对值: 1, 2, 3. 它们恰为 1、…、(p−1)/2 的一个排列
| 大于 p/2 的剩余个数 μ | 1 | Gauss 符号 (−1)^μ: −1 |
|---|---|---|
| a^((p−1)/2) mod p | 6 | Euler 符号: −1 |
| 模 p 的非零平方数 | 1, 2, 4 | 逐一检验的符号(a mod p 是否为平方数): −1 |
下取整和的奇偶
Σ ⌊a·i/p⌋ = 1; 下取整和的奇偶: 1; μ mod 2 = 1; 奇偶等于 μ 模 2: 是.
a 为奇数,奇偶论证适用:下取整和的奇偶必等于 μ 模 2,而结果正是如此。
a = q 为素数时的互反律矩形
点 (i, j) 满足 1 ≤ i ≤ (p−1)/2 及 1 ≤ j ≤ (q−1)/2。实心点在直线 q·i = p·j 之下,空心点在其上,没有点落在直线上。表格给出相同的计数。
| S1 = 对 i ≤ (p−1)/2 的 Σ ⌊q·i/p⌋ | 1 |
|---|---|
| S2 = 对 j ≤ (q−1)/2 的 Σ ⌊p·j/q⌋ | 2 |
| mn = ((p−1)/2)((q−1)/2) | 3 × 1 = 3 |
| S1 + S2 | 3 |
| S1 + S2 = mn | 是 |
| (q/p) = (−1)^S1 | −1 |
| (p/q) = (−1)^S2 | +1 |
两素数均模四余三,故 mn 为奇数,两个符号相反.
- p
- 7
- a
- 3
- m = (p−1)/2
- 3
- μ
- 1
- Gauss
- −1
- Euler
- −1
- 逐一检验
- −1
- 是否一致
- 是
p = 7,a = 3:μ = 1,Gauss 符号 −1,a^m ≡ −1(mod p),逐一检验符号 −1;一致:是。 Legendre 符号 (a/p) = −1; a 是模 p 的二次非剩余.
三个结论为何必然一致
把带符号代表元 t_i 相乘,模 p 得 a^m·m!;又因绝对值是 1、…、m 的排列,乘积恰为 (−1)^μ·m!。m! 不被 p 整除,可约去,得 a^m ≡ (−1)^μ。
Euler 判别准则指出平方数满足 a^m ≡ 1,非平方数满足 a^m ≡ −1,故符号 (−1)^μ 就是 Legendre 符号 (a/p)。逐一检验的名单是同一命题的独立核对。
对奇数 a,⌊a·i/p⌋ 对 i 求和的奇偶与 μ 只差一个偶数,这就是下取整公式。论证没有除以 2,并用到 a 与 p 均为奇数。
表格完整:每个 i ≤ (p−1)/2 各有一行,而 p 与 a 限于所述有限范围。它只核对所选的一组数值,不能取代证明。
反例模式
下取整和公式需要奇分子
一个诱人的说法是:对每个与 互素的分子都有 。取 、,则 ,而 ,预测符号为 。但模 的非零平方只有 与 ,所以 。Gauss 计数本身是正确的:剩余 中恰有一个大于 ,故 。奇偶步骤 用到 为奇数,在此失效。对 应改用补充计数 。
一个矩形完成互反律
证明
(计算矩形中的格点)
令 、。考虑 、 的 个整数点 。没有点在直线 上,否则由两不同素数的性质得 ,与范围矛盾。
固定 时,满足 的点数为 。由 ,它不超过 ;又无整数边界相等。固定 时同理, 的点数为 。两类互不相交且分割全部矩形,故
先对分子 ,再对分子 用下取整符号式,相乘得 ,正是互反律。每个格点只数一次,而没有边界点正是使用不同素数假设之处。直线两侧的点数不必相同。互反律使用的是两计数之和的奇偶,而非两计数相等;这也解释为何面积为奇数的矩形会产生相反符号。
证明透视
几何计数为何决定算术符号
这条推理链有三座桥,各用一个不同的假设。Gauss 引理把符号化为负代表元个数 的奇偶;它只需要 为奇数,使 为整数且 。下取整和恒等式则需要奇分子,因为它在模 下比较 与 。互反律把它用了两次,分子分别是 与 ,所以两个素数都必须是奇数。
关键一步是矩形。每个下取整和计算直线 一侧的格点;两素数相异保证没有格点落在直线上,所以两个计数之和恰为 。两侧的格点数不必相等:、 时两侧各有一点;、 时两个计数分别为 与 。只有总数的奇偶才重要,而特殊符号 正是矩形面积的奇偶。
例题详解
例题 6.1.4
(不找平方根也能计算符号)
求 。两素数均模四余一,故互反给 。乘法性化成 。由三十七模四余一,再互反得 。因此三十七是模一百零一的非零平方。这决定存在性,却未构造平方根;两者是不同任务。
例题 6.1.5
(先判剩余,再验证实际根)
对 ,互反符号为正,得到 。十三是根,因为 ;其负为二十八。两者互异且为全部根,因域上二次多项式至多两根。符号证存在,代入找到见证,根数界证完整。
例题 6.1.6
(合数符号不能取代素数定理)
对正奇整数 ,定义 Jacobi 符号 , 的空乘积为一。于是 。但二不是模十五平方,因任意候选根模三后都须平方为二,不可能。又 ,所以把 Euler 准则的 换成十五也失败。Jacobi 符号是局部符号乘积,并非完整的合数平方检验。
可靠的计算流程
先检查分子是否模素数为零,若是则符号零。否则选方便代表元,用已证恒等式分出负号、二因子或重复平方因子。对奇素因子互反,先记录负号再化简新分子。连续较小模数组织计算,但没有声称大分子的因数分解免费。
最后问符号究竟证明什么。正 Legendre 符号给非零目标两根,不给其公式;负符号排除根。正 Jacobi 乘积却可能留下不相容的局部符号。把判定、构造与完整性分开,可防止高效符号运算承担未证明的结论。
把非零平方根提升到奇素数幂
可控地离开域,仍有有用推广。固定奇素数 ,设 ,且 时 。此类到模 的每个提升均为 , 取模 。写 ,展开平方得提升为根当且仅当
余下 因 而模 消失。由 奇且 模 非零, 可逆,故 唯一。每个非零根因而唯一提升至所有更高幂。高模数根必化简成低模数根,所以这同时给存在与完整性,而非只列候选。
例如五模四十一的根十三有 。下一式为 ,解为 ,故 是模 的根:。其负给另一提升根。这是在已知素数层根后构造提升,互反律本身没有找到最初的根。
最后,正奇合数可分为不同素数幂因子,并假设目标与模数互素。按 Legendre 符号,每个素因子在所有幂次上不是无根,就是两根;中国剩余定理独立组合各选择。因此任一局部符号负便无根,否则恰有 根, 为不同素因子数。这不涵盖非单位目标或二的幂,因提升式的可逆性可能失效,也精确解释正 Jacobi 乘积为何弱于逐项检查局部符号。
常见错误
常见错误
(两素数都模 余 时漏掉负号)
对 ,两个素数都 ,所以互反律给出 。漏掉负号便得 ,这是错的:模 的非零平方是 ,其中没有 。
常见错误
(对合数或偶数分子使用互反律)
互反律联系的是两个相异的奇素数。像 这样的符号不能倒转为“”,后者不是 Legendre 符号。应先分解:,其中 用第二补充律,只有 用互反律。验算: 且 ,给出 。
Euler 准则是同余式,右边为整数零、一或负一;Gauss 引理则是符号等式。两者连接使用模奇素数时一与负一仍不同。合数环可能有额外的多项式根及非单位因子,因此两证明的域假设不可忽略。
总结
Euler 准则以符号编码平方性。Gauss 引理由带符号剩余置换取得符号,补充律处理负一及二,格点矩形给互反负号。完整证明可判定许多素数平方问题,同时清楚限制找根与合数结论的范围。
练习
快速检查
(计算 、,指出使用哪条补充律。)
解答 · 答案
,故 ;,故 。两者均用已证补充律,不是与偶素数互反。
快速检查
(计算 、;后者为正时,找出并验证 两根。)
解答 · 答案
、 均 ,所以 。另一对给 。根为 、,其平方 、 均 。两者互为负,域根数界排除其他根。
快速检查
(直接以 Gauss 引理算 ,列带符号代表元及负数个数。)
解答 · 答案
模 的正剩余为 ,带符号代表元为 。恰有一个负,故符号为 ;绝对值 明确展示所需置换。
快速检查
(证明若 ,且 是正奇数 模下的平方,则 Jacobi 符号为一;解释反向为何失败。)
解答 · 答案
对 每个素因子化简平方,由互素性得到非零平方,故全部 Legendre 因子均为 ,其幂乘积亦为 。 反驳逆命题:两个负局部符号相乘为正,但两局部平方式都无解。