二次剩余

考虑如下的二次同余方程 (`a, b, c` 为整数, `p` 为奇素数): `a x^2 + b x + c -= 0 (mod p)`. 由于 `p !| 4a`, 两边同乘 `4a` 得到等价的方程 `4a(a x^2 + b x + c) -= 0 (mod p)`, 配方, 即 `(2a x + b)^2 -= b^2 - 4a c (mod p)`. 可见, 模素数的二次同余方程归结为形如 `y^2 -= d (mod p)` 的同余方程, 即 `d` 关于模素数 `p` 开平方的问题. 这引出二次剩余的定义.

二次剩余的定义

设 `m` 为正整数, `(a, m) = 1`, 若同余方程 `x^2 -= a (mod m)` 有解, 则称 `a` 为 `m` 的二次剩余 (或 `a` 是模 `m` 的平方数, `a` 模 `m` 存在平方根). 否则, `a` 为 `m` 的二次非剩余.

求模 `m` 的所有平方根. 另外, 我们有 `O(log p)` 的算法来求一个数模素数 `p` 的平方根.

若 `x` 是 `a` 模 `m` 的平方根, 则任意 `x + k m (k in ZZ)` 也是平方根. 因此讨论二次剩余时, 只需考虑 `a in ZZ_m^** := { a in ZZ_m : (a, m) = 1 }`. 我们对同余的 `a` 不作区分, 在计算二次剩余的个数时, 也把同余的数视为同一个.
特别当模数 `m` 为奇素数 `p` 时, `a in ZZ_p^** = { bar 1, bar 2, cdots, bar (p-1) }`, 换言之, `p !| a`.

设 `p` 为奇素数, `a in ZZ_p^**`, 则 `a` 模 `p` 的平方根有 0 个或 2 个.

设 `n = p q` 是两个奇素数的乘积, 由孙子定理知道, 同余方程 `x^2 -= a (mod n)` 等价于 `x^2 -= a (mod p)`, `x^2 -= a (mod q)`. 因此原方程有解当且仅当 `a` 同时是 `p` 和 `q` 的二次剩余, 且这时 `a` 关于模 `n` 恰有 4 个平方根.

设 `p` 为奇素数, 则在集合 `ZZ_p^**` 中, 模 `p` 的二次剩余和非剩余各占一半.

`ZZ_p^**` 的元素可以写为 `+-1, +-2, cdots, +-(p-1)//2`, 恰好对应于 `1^2, 2^2, cdots, ((p-1)/2)^2`. 由上一个命题知道, 若 `x^2 -= y^2 (mod p)`, 则 `x -= +- y (mod p)`. 故以上 `(p-1)//2` 个数两两不相等, 即为模 `p` 的所有二次剩余.

利用 `ZZ_p^**` 中 `1` 的平方根只有 `+-1` 这个事实, 可以证明:

Wilson 定理 整数 `p ge 2` 为素数的充要条件是 `(p-1)! -= -1 (mod p)`.

必要性. `p = 2` 时显然成立. 下设 `p` 为奇素数, 在 `ZZ_p^**` 上考虑同余方程 `x y -= 1 (mod p)`. 对任意 `x`, 其逆元 `y` 是存在唯一的. 若 `x = y`, 则 `x` 是 `1` 在 `ZZ_p^**` 中的平方根, 即 `x = +-1`. 故 `ZZ_p^**` 的 `p-1` 个数中除 `+-1` 的逆元为自身外, 其它数字两两互逆, 因而它们的乘积抵消. 这 `p-1` 个数相乘得到 `(p-1)! -= 1 * (-1) -= -1 (mod p)`.
充分性. 设 `n = a b` 为合数, `1 lt a, b lt n`. 若 `(n-1)! -= -1 (mod n)`, 有 `(n-1)! -= -1 (mod a)`, 这与 `a | (n-1)!` 矛盾.

虽然 Wilson 定理也是素数的一种判别法, 但计算量巨大, 并不实用.

Legendre 符号

设 `p` 为奇素数, `a in ZZ_p^**`, 定义 Legendre 符号为 `(a/p) = { 1, if a " 是 " p " 的二次剩余"; -1, if a " 是 " p " 的二次非剩余" :}`

二次剩余的判别法

原根判别法 设 `p` 为奇素数, 取 `p` 的原根 `r`, 则 `ZZ_p^** = {1, r, cdots, r^(p-2)}`. 其中 `a = r^n` 是 `p` 的二次剩余当且仅当 `n` 是偶数. 这再次验证了二次剩余和非剩余各占一半的事实. 特别地, `(r/p) = -1`.

设 `n` 是偶数, 则 `r^(n/2)` 是 `a = r^n` 的平方根. 现在设 `x` 是 `a` 的一个平方根, 于是 `n = log_r a -= log_r x^2 -= 2 log_r x (mod varphi(p))`, 因此 `n` 是偶数.

Euler 判别法 `(a/p) -= a^((p-1)//2) (mod p)`. 即 `a` 为模 `p` 的二次剩余当且仅当 `sqrt a` 满足 Fermat 小定理, 亦即 `(sqrt a)^(p-1) -= 1 (mod p)`.

必要性显然, 下证充分性. 设 `(a/p) = -1`. 对每个 `x in ZZ_p^**`, 存在唯一的 `y in ZZ_p^**` 使得 `x y -= a (mod p)`, 因为 `a` 是模 `p` 的二次非剩余, 所以 `x != y`. 因此, 集合 `ZZ_p^**` 可以划分为 `(p-1)//2` 对, 每一对的乘积为 `a`. 由 Wilson 定理, `a^((p-1)//2) -= (p-1)! = -1 (mod p)`.

Euler 判别法是最常用的判别法, 使用快速幂, 时间复杂度为 `O(log p)`.

Legendre 符号 `(a/p)` 是关于 `a` 的积性函数: `(a/p)(b/p) = ((a b)/p)`, 特别地 `(a^2/p) = 1`.

对于素数 `p -= 3 (mod 4)`, 若 `a` 为 `p` 的二次剩余, 则同余方程 `x^2 -= a (mod p)` 的解为 `x = +-a^((p+1)//4)`.

平方得 `x = a^((p+1)//2)` `= a^((p-1)//2) * a` `= a`.

Gauss 判别法 `(a/p) = (-1)^s`, `s` 是 `A = {a, 2a, cdots, n a}` 中模 `p` 的绝对最小剩余为负的个数, `n = (p-1)//2`.

设 `A` 中元素的绝对最小剩余为 `a_1, a_2, cdots, a_n`. 由于 `A` 中元素均不是 `p` 的倍数, 因此这些余数只能取值 `+-1, +-2, cdots, +-n`. 下证 `|a_1|, |a_2|, cdots, |a_n|` 两两不同, 从而恰好构成 `1` 到 `n` 的一个排列.
若存在 `1 le i, j le n` 使得 `i a -= j a (mod p)`, 则 `i -= j (mod p)`. 若 `i a -= - j a (mod p)`, 则 `p | i + j`, 然而 `2 le i + j le 2n lt p`, 这是不可能的. 因此, `|a_1|, |a_2|, cdots, |a_n|` 两两不同.
将这些数相乘得到 `n! = prod_(i=1)^n |a_n|` `= (-1)^s prod_(i=1)^n a_n` `-= (-1)^s prod_(i=1)^n (i a)` `-= (-1)^s a^n n!` `(mod p)`, 即 `a^n -= (-1)^s (mod p)`. 再由 Euler 判别法即得结论.

-1 和 2 何时是二次剩余

`((-1)/p) -= p (mod 4)`.
换言之, 设 `p` 为奇素数, 方程 `x^2 + 1 -= 0 (mod p)` 有解当且仅当 `p` 形如 `4n+1`. 比如, `5 = 2^2+1`, `2*13 = 5^2 + 1`, `17 = 4^2 + 1` 等.

`(2/p)` `= (-1)^((p^2-1)//8)` `= { 1, p -= +-1 (mod 8); -1, p -= +-3 (mod 8) :}`.

二次互反律

这是初等数论中相当精彩的结论, Gauss 曾给出至少 6 个证明.

格点计数公式 设 `p` 为奇素数, `a` 为奇数, 则 `(a/p) = (-1)^Q`, `quad Q = sum_(i=1)^((p-1)//2) |__(a i)/p__|`. `Q` 是直线 `y = (a x)/p` 与 `x` 轴在区间 `[0, p/2]` 所围的三角形内部的格点数.

考虑 Guass 判别法中的集合 `A = {a, 2a, cdots, n a}`, `quad n = (p-1)//2`. 对任意 `1 le i le n`, 令 `r_i` 是 `a i` 模 `p` 的最小非负剩余, `a_i` 是 `a i` 模 `p` 的绝对最小剩余, 则 `r_i = { |a_i|, if a_i gt 0; p - |a_i|, if a_i lt 0 :}` 若 `a_i` 中负的有 `s` 个, 不妨设它们是 `a_1, cdots, a_s`, 则 `sum_(i=1)^n r_i` `= sum_(i=1)^s (p - |a_i|)` `+ sum_(i=s+1)^n |a_i|` `= s p - 2 sum_(i=1)^s |a_i| + sum_(i=1)^n |a_i|`. 由 Gauss 判别法知道 `|a_1|, cdots, |a_n|` 是 `1` 到 `n` 的排列, 故 `sum_(i=1)^n r_i = s p - 2 sum_(i=1)^s |a_i| + n(n+1)//2`. 令一方面由 `a i = p q_i + r_i` (`q_i = |__(a i)/p__|`) 求和有 `sum_(i=1)^n r_i = a n(n+1)//2 - p Q`. `quad Q = sum_(i=1)^n q_i`. 联系两式得到 `p(s + Q) = 2 sum_(i=1)^s |a_i| + (a-1) n(n+1)//2`. 由假设 `a` 是奇数, 故 `s + Q` 是偶数, 即 `s` 与 `Q` 奇偶相同. 因此 `(a/p) = (-1)^s = (-1)^Q`.

二次互反律 设 `p, q` 为不同的奇素数, 则 `(p/q)(q/p) = (-1)^((p-1)/2 (q-1)/2)`. 注意 `p -= 1 (mod 4)` 当且仅当 `(p-1)/2` 是偶数, 上式写为 `(p/q)(q/p) = { 1, if p -= 1 (mod 4) or q -= 1(mod 4); -1, if p -= q -= 3 (mod 4) :}` 即 `(p/q)` 与 `(q/p)` 符号相反当且仅当 `p, q` 都是 `4n+3` 型素数.

由格点计数公式 `(p/q)(q/p) = (-1)^(S + T)`, 其中 `S + T` 恰好为矩形 `(0, 0) - (p//2, q//2)` 内部的格点数 (由于 `p, q` 互素, 该矩形的对角线上没有格点). 于是 `S + T = (p-1)/2 (q-1)/2`.

二次互反律的 Euler 表述 设 `p, q` 为奇素数, `a in ZZ_p^**`. 则 `p -= +-q (mod 4a)` `rArr (a/p) = (a/q)`.

Jacobi 符号

现在我们考虑一般的模数 `m`.

Jacobi 符号 是 Legendre 符号的自然推广. 设 `m` 是正奇数, `a in ZZ_n^**`, Jacobi 符号定义为 `(a/m) = (a/(prod_(i=1)^r p_i^(s_i)))` `= prod_(i=1)^r (a/p_i)^(s_i)`. Jacobi 符号也是积性的.

若同余方程 `x^2 -= a (mod m)` 有解, 则 Jacobi 符号 `(a/m) = 1`. 反之不一定.

若 `x^2 -= a (mod m)`, 则对 `m` 的任意素因子 `p` 成立 `x^2 -= a (mod p)`, 因此 `(a/p) = 1`. `(a/m)` 是一系列 1 的乘积, 结果为 1.
考虑反例 `a = 2`, `m = 15`. 其 Jacobi 符号 `(2/15) = (2/3)(2/5) -= (-1) * (-1) = 1`. 但 `x^2 -= 2 (mod 3)` 无解, 因而 `x^2 -= 2 (mod 15)` 也无解.

设 `m = 2^(a_0) p_1^(a_1) cdots p_t^(a_t)`, `p_1, cdots, p_t` 为不同的奇素数, 则同余方程 `x^2 -= 1 (mod m)` 在 `ZZ_m^**` 中的解数为 `T = { 2^t, if a_0 = 0 or 1; 2^(t+1), if a_0 = 2; 2^(t+2), if a_0 ge 3; :}` 即 `1` 在 `ZZ_m^**` 有 `T` 个平方根.