为什么只处理单位不够
对奇素数 ,现有二次剩余笔记处理与 互素的目标。若目标可被 整除,根也可能可被 整除,因此导数 不再模 可逆;直接套用单位根的提升步骤会忽略情况的变化。
我们每次只处理一个奇素数幂。以下 为奇素数、;除另有注明外,同余模数均为 。
定义 6.2.1
( 进赋值)
对非零整数 , 是使 的最大整数 。于是 ,其中 ,并且 。若 ,则 。我们不给 指定有限赋值。
模素数幂非零的目标
定理 6.2.2
(非零目标下 的根)
设 ,其中 、。同余式 有解当且仅当 为偶数且 是模 的平方。此时它恰有 个模 的根,而且每个根都满足 。
证明
(赋值、缩小的模数与提升)
根的赋值。 若 ,则 且 ;否则 整除 ,因同余也整除 ,与 矛盾。两个小于 的赋值必须相等:若不同, 的赋值会等于较小者,与它可被 整除矛盾。故 ,所以 必为偶数,设为 ;若 为奇数便没有解。
简化条件。 当 ,写 ,其中 。除以 后得到等价的简化条件
除法改变了模数,不能保留模 直接约去。
单位方程。 若 模 不是平方,由于 ,便没有根。若 是模 的非零平方,则对每个 ,单位方程恰有两个模 的根。事实上模 有两个根 ,因 为奇数而互不相同。若 是模 的根,其提升 满足
奇素数模下 可逆,故恰有一个 使提升仍是根;归纳即得结论。
计数。 令 。模 而 的剩余类 ,经 恰好对应一个模 的单位剩余类 。因为 ,模 的两个根各有 个模 的提升,而它们都是简化条件的根。因此原同余恰有 个根。
证明透视
假设在计数中何处介入
证明只有一个不显然的步骤:除以 之后, 的条件只在模 下成立,但根 只由 模 决定。中间相差的 个 的幂是自由的,计数中的因子 正是由此而来。
假设 只用了一次:排除平方可被 整除的根,使目标能够决定每个根的赋值。 为奇数则用了两次:使模 的两个根互不相同,并使 可逆,从而每个根唯一提升。若没有这个假设,连单位目标的计数也会失效:模 时, 有 四个根,而不是两个。
零目标
定理 6.2.3
( 的根)
的根恰好是可被 整除的剩余类,包括 ,共有 个。
证明
(平方的整除条件)
对 , 即 ,也即 ;零剩余类也是根。模 下可被 整除的剩余类共有 个。零不能通过指定小于 的有限赋值 来处理。
例子
例题 6.2.4
( 的六个根)
这里 、、、、。令 ,简化条件是 ,其根为 。每个根有三个模 的提升: 与 。乘以三得到模 的六个不同根:
例如 。数量 证明列表完整。相反, 没有解,因为目标的赋值是一。
例题 6.2.5
(赋值为偶数但单位部分不是剩余)
考虑 。这里 ,所以 、、,赋值检验通过。写 并除以 ,得 。模 的平方只有 与 ,所以没有根。定理的两个条件缺一不可:赋值为偶数,而且单位部分是平方。
例题 6.2.6
(模 的零目标)
对 ,有 、,所以根是 的倍数:
共有 个。例如 ,但 。这个数目是奇数,所以不可能来自非零目标的成对计数 。
常见错误
反例模式
缩减目标后不能保留原模数
声称: 的根,是 而 。后者只有 与 两个根,给出 与 。但 ,而 。这个说法漏掉了六个根中的四个。除以 时模数也须一并除以 :正确的条件是 。
常见错误
(两个根只是单位目标的数目)
模奇素数幂时,单位目标的根数是零或二。对赋值为 的非零目标,根数是 : 有六个根,不是两个。只找到 两个根便停下,会漏掉其他提升。
常见错误
(把零目标当作赋值为 )
把 代入非零目标的公式并不成立。对 ,它会给出 个根,但正确数目是 。
练习
快速检查
( 有多少个模 的根?)
解答 · 答案
根是 的倍数,共 个剩余类。
快速检查
( 有解吗?)
解答 · 答案
没有。目标模 非零,赋值为奇数 ,但根必须满足 。
快速检查
(求 的所有模 根。)
解答 · 答案
写 ,则 ,故 。取模 的 ,得 ,根为 ,即 个根。
快速检查
(为什么单位根的提升论证需要 为奇数?)
解答 · 答案
只有 为奇数时,单位根的 才模 可逆。 时因子二不可逆,唯一提升的证明不适用;模 时 有四个根。这本身并不分类二的幂次模数的情况。