两数之和的奇偶性练习附答案（数论之酿母二次互反律）

两数之和的奇偶性练习附答案（数论之酿母二次互反律）则称 n 为 模m 二次剩余，否则称为 模 m二次非剩余。显然，某二次数 模 m 的余数，本身就是 模 m 二次剩余。x² ≡ n (mod m) ☆这些数都是 某个整数的 平方，故我们称它们为 二次数。给定任意正整数 m，对任意二次数 x²，进行带余数除法，有，x² = ym r (0≤ r＜m)其中，r 称为余数，它是 模运算 x² mod m 的结果，故 一个非零的余数 r 就是 二次数 模 m 的剩余。若 整数 n 模 m 的剩余 是 某 二次数 x² 模 m 的 剩余 r，即，n 和 某个二次数 x² 模 m 同余数，记为，

话题：#科学 #数学# #科技# #算法#

小石头/编

---

在整数中，能够开平方后还是整数的数有：

0 1 2² ⋯ x² ⋯

这些数都是 某个整数的 平方，故我们称它们为 二次数。给定任意正整数 m，对任意二次数 x²，进行带余数除法，有，

x² = ym r (0≤ r＜m)

其中，r 称为余数，它是 模运算 x² mod m 的结果，故 一个非零的余数 r 就是 二次数 模 m 的剩余。若 整数 n 模 m 的剩余 是 某 二次数 x² 模 m 的 剩余 r，即，n 和 某个二次数 x² 模 m 同余数，记为，

x² ≡ n (mod m) ☆

则称 n 为 模m 二次剩余，否则称为 模 m二次非剩余。显然，某二次数 模 m 的余数，本身就是 模 m 二次剩余。

这里需要注意，不管是 二次剩余 还是 二次非剩余，都必须有剩余，也就是说 ，前提是 n mod m ≠ 0 ，即，m 不整除 n（记为 m ∤ n），而 当 m 整除 n（记为 m | n） 时，则有 n mod m = 0 ，故此时的 n 既不是二次剩余，也不是二次非剩余，可称为 模 m 无剩余。

※ 举个栗子 ⑴：

由于 9 mod 5 = 4 = 2² = 2² mod 5，所以 9 是 模5二次剩余；由于 10 mod 5 = 0，所以 10 是 模5无剩余；而 8 mod 5 = 3，可以证明 3 不是任何二次数模5的剩余，故 8 是 模5的二次非剩余。

---

那么，是如证明 3 不是 二次数模5的剩余的呢？

若 将 ☆ 看成 方程（称为，同余方程，要求解必须是整数）， 在 m ∤ n 的前提下，则 n 是二次剩余 当且仅当 方程 ☆ 有解（同时，n 是二次非剩余 当且仅当 方程 ☆ 无解）。

设 x₀ 是方程☆的一个解，由于 对于任意 整数 k 有，

(km ± x₀)² = k² m² ± 2x₀km x₀² ≡ x₀² ≡ n (mod m)

故 (km ± x₀) 也都是 ☆ 的解 ①。

再考虑 带余除法 x₀ = tm r，若 1 ≤ r ≤ m/2，则令 x₁ = r = (-t)m x₀，若 m/2 < r < m，则令 x₁ = m - r = (t 1)m - x₀，这样以来 1 ≤ x₁ ≤ m/2，并且 根据结论 ①，x₁ 也是☆的解。

也就是说，

■ 方程☆有解，当且仅当，存在 1 ≤ x₁ ≤ m/2 是其解。

这样以来，

■ 1 mod m 2² mod m ⋯ [m/2]² mod m 将包含 全部的 二次数 模m 的剩余。②

其中 [*] 表示对 * 向下取整，例如：[5/2] = [2.5] = 2。

根据结论 ②，栗⑴中全部 二次数 模5 的剩余 的剩余 只有：

1 mod 5 = 1 2² mod 5 = 4

而 3 显然不在此例，这样就证明了 3 不是 二次数模5的剩余。

---

一般情况下，我们很难保证 ② 的数列中，不出现 相同 或 为零 的可能，例如：

3² mod 8 = 1 = 1 mod 8， 3² mod 9 = 0，

但当 m 是 素数 p 时，却可以保证，而且 若 p 是奇数时，有 [p/2] = (p-1)/2，故此时，

■ 1 mod p 2² mod p ⋯ ((p-1)/2)² mod p 就是 全部的 (p-1)/2 个 二次数 模p 的剩余。

为啥 素数 可以保证呢？这是因为：

• 若存在 1 ≤ a ≠ b ≤ (p-1)/2，使得 a² mod p = b² mod p ，则 p | (a² - b²)=(a - b)(a b)，由于 p 是素数，故要么 p|a - b 要么 p|a b，可是 0 < |a ± b| < p ，故 都不可能；

• 若存在 1 ≤ a ≤ (p-1)/2 使得 p|a²=aa，则由于 p 是素数，故 p|a，可是 0 < a < p，故这也不可能。

鉴于，素数 有如此良好的 品质，所以 接下来我们将重点研究 模 是素数的情况。

---

为了表述方便，我们引入勒让德（Legendre）符号（伪定义）：

这样，栗⑴的结果可写为，

(9|5) = 1 (10|5) = 0 (8|5) = -1

有了，勒让德符号后，判断 二次剩余问题，就转变为求 勒让德符号了。

求 勒让德符号 (n|m) 当然 可以算出 ② 中所有的 模 m 二次剩余，然后根据 n 是否与之其一 同余数 来进行判断，这写成Haskell 代码如下：

legendre :: Integer -> Integer -> Integer legendre n m = if (r == 0) then 0 else (loop 1) where r = mod n m loop i | i <= (div m 2) = if ((mod (i*i) m) == r) then 1 else (loop (i 1)) | otherwise = -1

但是这个方法比较适合计算机，若是人来计算随着 m 的曾大，效率就会极具降低，那么有没有更简便的计算方法呢？

---

我们知道素数分为 偶素数 2 和 奇素数，对于 偶素数 2 来说，根据 ② 可求出，其全部二次余数为，

1 mod 2 = 1

没有二次非余数。于是，只要 n 是奇数 则 一定 n ≡ 1 (mod 2)，进而 n 是 模2 二次剩余，否是，必然是 模2 无剩余的。这非常简单，所有说，重点是 m 是 奇素数 p 的情况。

实际上，前面勒让德符号的定义是为了讨论方便，此时 才是 勒让德符号的正规定义，即，对于 奇素数 p 定义（真定义）：

而，对于 奇数 m 的，当 (m n) = 1时，设m的素因子分解为 m = p₁p₂ ⋯pᵣ，定义：

称为 雅克比符号。

---

由于 p 是素数，所以 要么 p | n 要么 p ∤ n 。

● 先讨论 p ∤ n 的情况：

由于 p 是素数，所以这时有 (n p) = 1，于是，

• 当 (n|p) = 1 时，存在 1 ≤ a ≤ (p-1)/2 使得 a² ≡ n (mod p) ，而由于 0 < a < p，p是素数，所以 (a p) = 1 于是 根据 著名的 费马小定理有，

aᵖ⁻¹ ≡ 1 (mod p)

进而有，

n⁽ᵖ⁻¹⁾ᐟ² ≡ (a²)⁽ᵖ⁻¹⁾ᐟ² = aᵖ⁻¹ ≡ 1 (mod p)

即得到，

n⁽ᵖ⁻¹⁾ᐟ² ≡ 1 (mod p)

反过来，可以证明，

□ 若 n⁽ᵖ⁻¹⁾ᐟ² ≡ 1 (mod p) 成了，则 x² ≡ n (mod p) 有解，

进而 (n|p) = 1。

综上我们得到，

A： (n|p) = 1 当且仅当 n⁽ᵖ⁻¹⁾ᐟ² ≡ 1 (mod p)

• 当 (n|p) = -1 时， 由于 (n p) = 1，根据费马小定理有，

nᵖ⁻¹ ≡ 1 (mod p)

于是，

(n⁽ᵖ⁻¹⁾ᐟ² -1)(n⁽ᵖ⁻¹⁾ᐟ² 1) = nᵖ⁻¹-1 ≡ 0 (mod p)

由于 p 是素数，故 要么 n⁽ᵖ⁻¹⁾ᐟ² -1 ≡ 0 (mod p) 要么 n⁽ᵖ⁻¹⁾ᐟ² 1 ≡ 0 (mod p)，而 若是前者，则有 n⁽ᵖ⁻¹⁾ᐟ² ≡ 1 (mod p) 根据 欧拉判则 会得出 (n|p) = 1 矛盾！ 故 只能是 后者，从而得到，

n⁽ᵖ⁻¹⁾ᐟ² ≡ -1 (mod p)

也就是说，我们得到，

B： 若 (n|p) = -1 则 n⁽ᵖ⁻¹⁾ᐟ² ≡ -1 (mod p)

● 再讨论 p | n 的情况：

此时 只能 有 (n|p) = 0，并且有，

n ≡ 0 (mod p)

于是，

n⁽ᵖ⁻¹⁾ᐟ² ≡ 0 (mod p)

进而我们得到，

C：若 (n|p) = 0 则 n⁽ᵖ⁻¹⁾ᐟ² ≡ 0 (mod p)

最后，综合 A、B 和 C 三种情况，最终得出如下公式：

■ (n|p) ≡ n⁽ᵖ⁻¹⁾ᐟ² (mod p)

这称为 欧拉（Euler）判则。

根据 欧拉判则 很容易得出：

---

勒让德符号，其实和符号函数很像，

对于符号函数来说有 sign(ab) = sign(a)sign(b)，那么勒让德符号呢？根据 欧拉判则 有，

(ab | p) ≡ (ab)⁽ᵖ⁻¹⁾ᐟ² = a⁽ᵖ⁻¹⁾ᐟ²b⁽ᵖ⁻¹⁾ᐟ² ≡ (a | p) (b | p) (mod p)

注意到 p 是奇素数，有 | (ab | p)|，|(a | p) (b | p) | < 2 < p，故得到，

■ (ab | p) = (a | p) (b | p)

我们称 这种性质 为 完全积性。

当 n 的素因子分解为 n = ±2ˢ q₁ᵉ¹⋯qᵣᵉʳ 时，根据 安全积性 有，

(n | p) = (±1 | p) (2 | p)ˢ(q₁ | p)ᵉ¹⋯(qᵣ | p)ᵉʳ

也就是说，我们只要找到求 (±1 | p)、(2 | p) 和 (q | p) （q 为奇素数）的公式，就等于得到了 求任意 勒让德符号 的 公式。

其中 求 (±1 | p) 已经在前面给出了，现在我们来求 (2 | p) 。考虑 模p的所有非零偶数余数的乘积，有，

2⋅4⋅⋯⋅(p-3)⋅(p-1) = (2⋅1)⋅(2⋅2)⋅⋯⋅(2⋅(p-3)/2)⋅(2⋅(p-1)/2) = 2⁽ᵖ⁻¹⁾ᐟ²(1⋅2⋅⋯⋅(p-3)/2⋅(p-1)/2) = 2⁽ᵖ⁻¹⁾ᐟ²((p-1)/2)!

另一方面，还有，

2⋅4⋅⋯⋅(p-3)⋅(p-1) ≡ 2⋅4⋅⋯⋅(-3)⋅(-1) = ((-1)²⋅2)⋅((-1)⁴⋅4)⋅⋯⋅((-1)³⋅3)⋅((-1)¹⋅1) =((-1)¹⋅(-1)²⋅(-1)³⋅(-1)⁴⋅⋯⋅(-1)⁽ᵖ⁻¹⁾ᐟ²)(1⋅2⋅⋯⋅(p-3)/2⋅(p-1)/2) = (-1)¹⁺²⁺³⁺⁴⁺˙˙˙⁺⁽ᵖ⁻¹⁾ᐟ²((p-1)/2)! = (-1)⁽ᵖ⁺¹⁾ᐟ⁴ ((p-1)/2)! (mod p)

故有，

2⁽ᵖ⁻¹⁾ᐟ²((p-1)/2)! ≡ (-1)⁽ᵖˆ²⁻¹⁾ᐟ⁸ ((p-1)/2)! (mod p)

由 p ∤ ((p-1)/2)! 有 ((p-1)/2)! ≢ 0 (mod p) ，于是等式两边消去 ((p-1)/2)! 得到，

2⁽ᵖ⁻¹⁾ᐟ² ≡ (-1)⁽ᵖˆ²⁻¹⁾ᐟ⁸ (mod p)

又 由 欧拉判则 知，

(2 | p) ≡ 2⁽ᵖ⁻¹⁾ᐟ² (mod p)

于是有，

(2 | p) ≡ (-1)⁽ᵖˆ²⁻¹⁾ᐟ⁸ (mod p)

而 |(2 | p)| |(-1)⁽ᵖˆ²⁻¹⁾ᐟ⁸| < p，故最终得到 ③，

---

现在考虑 (q | p) 的求解问题。我们知道，对于符号函数有（n≠0） ，

sign(n)sign(n) = 1，sign(n)sign(1/n) = 1

因此，

1sign(1/n) =sign(n)sign(n)sign(1/n) = sign(n)1

于是得到，

sign(1/n) = sign(n)

这样， 求解较为复杂 sign(1/n) 的问题，就转为 求解较为简单的 sign(n) 的问题了 （注：这仅仅是引入个思想，大家不要叫真： sign(1/n) 是否真比 sign(n) 复杂）。

而对于 勒让德符号有，

(q | p)(q | p) ≡ q⁽ᵖ⁻¹⁾ᐟ²q⁽ᵖ⁻¹⁾ᐟ² = qᵖ⁻¹ ≡ 1 (mod p) ⇒ (q | p)(q | p) = 1

如果 还能找到，关系式，

(p | q) (q | p) = 〈exp〉

则，同理 可以得到

(q | p) = (p | q)〈exp〉

这样，(p | q) 中 (q | p) 较难的那个，就可以通过较容易的那个求解了。

这个要找的关系式，就是 由欧拉首次提出，被高斯首次证明的，数论中的宝石，黄金律之一，有着 数论之酿母 之称 的 二次互反律 （设 p≠q 是奇素数）：

下面让我们看看，高斯是如何证明的。

---

首先，对求解 (2 | p) 的方法进行扩展，考虑 从 1 到 (p-1)/2 倍的n 的余数，

n mod p 2n mod p ⋯ ((p-1)/2)n mod p

若 (p n) = 1，则可以保证上面的 (p-1)/2 个余数 不重复。p/2 可以把其分为两部分，表示为，

a₁ a₂ ⋯ aᵤ < p/2 < b₁ b₂ ⋯ bᵥ

其中，u v = (p-1)/2，并且有，

(a₁⋅a₂⋅⋯⋅aᵤ)⋅(b₁⋅b₂⋅⋯⋅bᵥ) ≡ n⋅2n⋅⋯⋅ ((p-1)/2)n = n⁽ᵖ⁻¹⁾ᐟ²((p-1)/2)! (mod p)

再令，

c₁=p-b₁ c₂=p-b₂ ⋯ cᵥ=p-bᵥ

则 c₁ c₂ ⋯ cᵥ < p/2，并且 aᵢ ≠ cj ，否则：

必然存在 1≤ s t < (p-1) ≤/2 使得 sn ≡ p-tn (mod p) 于是 (s t)n ≡ p ≡ 0 (mod p) 这说明 s t = kp，可是 0 < 2 ≤ s t < p-1 < p，故不可能。

这样一来，a₁ a₂ ⋯ aᵤ c₁ c₂ ⋯ cᵥ 就是全部的 1 到 (p-1)/2 的余数，于是有，

((p-1)/2)! = (a₁⋅a₂⋅⋯⋅aᵤ)⋅(c₁⋅c₂⋅⋯⋅cᵥ) = (a₁⋅a₂⋅⋯⋅aᵤ)⋅((p-b₁)⋅(p-b₂)⋅⋯⋅(p-bᵥ)) ≡ (a₁⋅a₂⋅⋯⋅aᵤ)⋅((-b₁)⋅(-b₂)⋅⋯⋅(-bᵥ)) = (-1)ᵛ⋅(a₁⋅a₂⋅⋯⋅aᵤ)⋅(b₁⋅b₂⋅⋯⋅bᵥ) ≡ (-1)ᵛn⁽ᵖ⁻¹⁾ᐟ²((p-1)/2)! (mod p)

等式两边消去 p ∤ ((p-1)/2)! 得到，

1 ≡ (-1)ᵛn⁽ᵖ⁻¹⁾ᐟ² (mod p)

等式两边乘以 (-1)ᵛ，并结合欧拉判则有，

(-1)ᵛ = (-1)ᵛ1 ≡ (-1)ᵛ(-1)ᵛn⁽ᵖ⁻¹⁾ᐟ² = ((-1)²)ᵛn⁽ᵖ⁻¹⁾ᐟ² = 1ᵛn⁽ᵖ⁻¹⁾ᐟ² = n⁽ᵖ⁻¹⁾ᐟ² ≡ (n | p) (mod p)

由于，-p < (n | p) -1 < p， 故最终得到，

■ (n | p) = (-1)ᵛ

于是高斯 得到了 一个 引理。

然后，观察 取值于 1 ≤ x ≤ (p-1)/2，1 ≤ y ≤ (q-1)/2 的整数函数，

f(x y) = qx - py

若 f(x y) = f(x' y') 则，

qx - py = qx' - py'

q(x-x') = p(y - y')

由于 q 和 p 都是不同素数，故

p | x-x' q | y-y'

又 |x - x'| < p |y - y'| < q 所以只能是 x - x' = 0， y - y' = 0 即，x=x'， y - y' 。这就是说明 f(x y) 的值各不相同，共有 ((p-1)/2) ((q-1)/2) 个。

另一方面，假设 f(x y) = qx - py= 0 ，则 qx = py ，于是 p | x， q | y，而 0 < x < p 0 < y < q，因此不可能！所以 f(x y) ≠ 0，于是 f(x y) 的值 分为 大于 0 与 小于 0 两部分：

• 固定 x ，若 f(x y)=qx - py > 0 则 y < qx/p，即 y ≤ [qx/p] ，于是 f(x y) 的值 大于 0 的个数为 ∑x=1⁽ᵖ⁻¹⁾ᐟ² [qx/p]；
• 同理，固定 y，若 f(x y)=qx - py < 0 则 x < py/q，即 x ≤ [py/q]，于是 f(x y) 的值 小于 0 的个数为 ∑y=1⁽ᶣ⁻¹⁾ᐟ² [px/q]。

综上的就得到关系式：

■ ∑x=1⁽ᵖ⁻¹⁾ᐟ² [qx/p] ∑y=1⁽ᶣ⁻¹⁾ᐟ² [px/q] = ((p-1)/2) ((q-1)/2)

最后，开始正式证明。

利用引理来计算 (q | p) ，根据引理推导过程有，

∑x=1⁽ᵖ⁻¹⁾ᐟ² x = 1 2 ⋯ (p-1)/2 = (a₁ a₂ ⋯ aᵤ) (c₁ c₂ ⋯ cᵥ) = (a₁ a₂ ⋯ aᵤ) ((p-b₁) (p-b₂) ⋯ (p-bᵥ)) = (a₁ a₂ ⋯ aᵤ) vp - (b₁ b₂ ⋯ bᵥ)

另，结合带余除法有，

( ∑x=1⁽ᵖ⁻¹⁾ᐟ² x)q = ∑x=1⁽ᵖ⁻¹⁾ᐟ² xq = ∑x=1⁽ᵖ⁻¹⁾ᐟ²( [xq/p]p xq mod p） = ∑x=1⁽ᵖ⁻¹⁾ᐟ²[xq/p]p ∑x=1⁽ᵖ⁻¹⁾ᐟ² xq mod p= p∑x=1⁽ᵖ⁻¹⁾ᐟ²[xq/p] (a₁ a₂ ⋯ aᵤ) (b₁ b₂ ⋯ bᵥ)

注意到 ∑x=1⁽ᵖ⁻¹⁾ᐟ² = (p²-1)/8，于是上面的两式相减得到，

((p²-1)/8)(q-1) = p∑x=1⁽ᵖ⁻¹⁾ᐟ²[xq/p] - vp 2 (b₁ b₂ ⋯ bᵥ)

由于 p q 都是 素数，所以 p ≡ q ≡ 1 (mod 2)，于是 对上式 模 2 有，

((1²-1)/8)(1-1) ≡ 1 ∑x=1⁽ᵖ⁻¹⁾ᐟ²[xq/p] - v1 0(b₁ b₂ ⋯ bᵥ) (mod 2)

0 ≡ ∑x=1⁽ᵖ⁻¹⁾ᐟ²[xq/p] - v (mod 2)

即得到，

v = ∑x=1⁽ᵖ⁻¹⁾ᐟ²[xq/p] (mod 2)

于是有，

v = 2k ∑x=1⁽ᵖ⁻¹⁾ᐟ²[xq/p]

再根据 引理，有，

(q | p) = (-1) ᵛ = (-1)^{2k ∑x=1⁽ᵖ⁻¹⁾ᐟ²[xq/p] } = (-1)^{∑x=1⁽ᵖ⁻¹⁾ᐟ²[xq/p] }

同理可求得，

(p | q) = (-1)^{∑y=1⁽ᶣ⁻¹⁾ᐟ²[yp/q] }

注：由于上标 q 在有些OS中无法正常显示，所以 这里 用 ᶣ 表示上标 q。

于是结合上面的关系式，有，

(q | p) (p | q) = (-1)^{∑x=1⁽ᵖ⁻¹⁾ᐟ²[xq/p] } (-1)^{∑y=1⁽ᶣ⁻¹⁾ᐟ²[yp/q] } = (-1)^{∑x=1⁽ᵖ⁻¹⁾ᐟ²[xq/p] ∑y=1⁽ᶣ⁻¹⁾ᐟ²[yp/q] } = (-1)⁽⁽ᵖ⁻¹⁾ᐟ²⁾⁽⁽ᶣ⁻¹⁾ᐟ²⁾

得证！

---

至此，我们对于 奇素数模p 的勒让德符号计算问题，就全部搞清楚了。

※ 举个栗子⑵：

求 (520 | 7) ？

先对 520 进行素因子分解，

520 = 5⋅4⋅2⋅13 = 2³⋅5⋅13

再根据完全积性 和 二次互反律，有，

(520 | 7) = (2 | 7)³(5 | 7)(13 | 7) = (2 | 7)³(7 | 5)(-1)⁽⁽⁵⁻¹⁾ᐟ²⁾⁽⁽⁷⁻¹⁾ᐟ²⁾(6 | 7) = (2 | 7)³(2 | 5)(-1)⁶(2⋅3 | 7) = (2 | 7)⁴(2 | 5)(3 | 7) = (2 | 5)(3 | 7) = (2 | 5)(7 | 3)(-1)⁽⁽³⁻¹⁾ᐟ²⁾⁽⁽⁷⁻¹⁾ᐟ²⁾ = (2 | 5)(1 | 3)(-1)³ = (-1)(2 | 5)(1 | 3)

注意：(n | p) = (n mod p | p)

根据 ③ ，由 5 ≡ -3 (mod 8) 有 (2 | 5) = -1，而显然 (1 | 3) = 1，故最终计算出，

(520 | 7) = (-1)(2 | 5)(1 | 3) = (-1)(-1)1 = 1

用计算机验证，

*Main> legendre 520 7 1

OK！

---

最后，我们来看看 模 m 是素数方幂 的 n 的 二次剩余判断。

● 先看 模是 偶素数 2 方幂：

• 对于 2² 来说，由，

1 mod 2² = 1 2² mod 2² = 0

故全部二次余数依然只有 1，但是有 二次非余数有 2 3。于是：

■ 当 n 是奇数 时， n 是 模2² 二次剩余 当且仅当 n ≡ 1 (mod 2²)。

• 对于 2³ 来说，由，

1 mod 2³ = 1 2² mod 2³ = 4 3² mod 2³ = 1 4² mod 2³ = 0

有全部二次余数是 1 4。当 n 是奇数 时，设 n = 2y 1，有，

• 若 y = 2²k，则 n = 2(2²k) 1 = 2³k 1 ≡ 1 (mod 2³)
• 若 y = 2²k 1，则 n = 2(2²k 1) 1 = 2³k 3 ≡ 3 (mod 2³)
• 若 y = 2²k 2，则 n = 2(2²k 1) 1 = 2³k 5 ≡ 1 (mod 2³)
• 若 y = 2²k 3，则 n = 2(2²k 3) 1 = 2³k 7 ≡ 3 (mod 2³)

可见，此时，

■ n 是 模2³ 二次剩余 当且仅当 n ≡ 1 (mod 2³)。

• 对于 2ˢ（s≥3）来说，我们可以证明：

□ 当 n 是奇数 时， x² ≡ n (mod 2ˢ) 有解 当且仅当 x² ≡ n (mod 2³) 有解， ④

故 此时，

■ n 是 模2ˢ 二次剩余 当且仅当 n ≡ 1 (mod 2³)。

● 再看 模是奇素数 p 方幂：

其实 我们还能证明（s≥1），

□ x² ≡ n (mod pˢ) 与 x² ≡ n (mod p) 同解，⑤

于是 根据 前面 的 A，有，

■ n 模 pˢ 二次剩余 当且仅当 n⁽ᵖ⁻¹⁾ᐟ² ≡ 1 (mod p)

---

至此，就是剩下 m 是 普通合数的二次剩余判断了，这个就比较复杂了，以后有时间再讨论。

而我们今天讨论二次剩余判断主要是为了引入 二次互反律，二次互反律的重要性，在于它在数论中的应用，不过这需要结合具体问题来讨论，就不在这里讨论了。

可以这样认为，初等数论的起始，有三重门：

素数 → 同余 → 二次剩余

而：

算术基本定理、费马小定理 和 二次互反律

分别是 每个 门里 的 黄金律。

只有，闯过这三重门，才能真正 进入初等数论 世界。当然，在这之后还有，更多的 门，例如：原根、卢卡斯序列 等。其中 原根这道门里，就藏着 证明 ④ ⑤ 的方法。

初等数论 是一个美妙的世界，是数学之美 的享受，是数学爱好者 的天堂！也许 520 更应该把它送给你的至爱吧？