二次剩余和 Gauss 互反律

从二次剩余问题，引入 Legendre 符号，由此一步步导出 Gauss 互反律，最后延伸到 Jacobi 符号，整个步骤确实连贯优美，脍炙人口。

寒假回家好好调整了一下状态，回学校后感觉还不错，效率也蛮高。发现理图虽然比较破，但是还是很不错的，哈哈哈。每次读潘承洞先生的《数论基础》都觉得受益匪浅，我把自己很喜欢的部分写入到该文中。

二次剩余

考虑如下形式二次同余式

$x^2 \equiv a \; \mod \; p$

其中 $p$ 是奇素数，$a$ 是非负整数。若上述方程有解，则称 $a$ 是 $p$ 的二次剩余，记作 $a\; R \; p$，否则称 $a$ 是 $p$ 的二次非剩余，记作 $a \; \overline{R}\; p$ 。$p=2$ 时就没啥意思了，所以 仅考虑奇素数。

经过简单推理很容易发现，在模 $p$ 的简化系中，二次剩余与二次非剩余各占一半。且容易知道，$1^2,2^2,\cdots,(\frac{p-1}{2})^2$ 都是 $p$ 二次剩余。

Legendre 符号

$\left( \frac{a}{p} \right) = \left\{ \begin{array}{cc} 1, & a\; R\; p \\ 0, & p \mid a \\ -1, & a\; \overline{R}\; p. \end{array} \right.$

定理 1: $ \quad -(\frac{a}{p}) (p-1)! \equiv a^{\frac{p-1}{2}} \mod p $

Proof: 对于 $p \mid a$ 的情形，结论显然。下面考虑 $(p,a)=1$ 的情形，令

$S = \lbrace 1,2,\cdots,p-1 \rbrace$

对任意的 $ x \in S $ 必存在唯一的 $ y \in S $ 为下面同余式的解

$yx \equiv a \; \mod p$

当 $ (\frac{a}{p}) = -1 $ 时，同余式 $ x^2 = a \; \mod p$ 无解，所以 $y \neq x $ .因此集合 $S$ 中的元素可以分成 $\frac{p-1}{2} $ 对，我们就有

$(p-1)! \equiv a^{\frac{p-1}{2}} \;\mod p$

当 $ (\frac{a}{p}) = 1 $ 时，同余式 $ x^2 = a \; \mod p $有两个解 $x_0$ 和 $p - x_0$.在$S$中去掉这两个数外剩下$p-3$个数分出 $\frac{p-3}{2}$对，则有

$(p-1)! \equiv a^{\frac{p-3}{2}}x_0(p-x_0) \equiv - a^{\frac{p-1}{2}} \; \mod p$

证毕。

推论 2 (Wilson 定理)

$(p-1)! \equiv -1 \;\mod p$

Proof: 定理 1 中取 $a=1$ 即可。

推论 3(Euler 判别法)

$\left( \frac{a}{p} \right ) \equiv a^{\frac{p-1}{2}} \; \mod \;p$

Proof: 由 定理 1 和 推论 2 显然。Euler 判别法不仅有理论价值(下面都是推论 3 的直接推论)，由于快速幂的存在，使得 Euler 判别法在计算时有相当好的效果。

推论 4(Format 小定理) 设 $(a,p)=1$ ,则

$a^{p-1} \equiv 1 \;\mod p$

推论 5：$(\frac{-1}{p}) = (-1)^{\frac{p-1}{2}}$

推论 6：$(\frac{ab}{p}) =(\frac{a}{p})(\frac{b}{p}) $

推论 6 说明，我们求 Legendre 符号，只需求 $ (\frac{2}{p}),(\frac{q}{p}) $ 即可

定理 7：$(\frac{2}{p}) = (-1)^{\frac{p^2-1}{8}}$

Proof:

$2^{\frac{p-1}{2}}(\frac{p-1}{2})! = 2 \cdot 4 \cdots (p-1) \equiv (\frac{p-1}{2})!(-1)^{1+2+\cdots+\frac{p-1}{2}}\;\mod p$

其中最后一个等价是因为：

$\begin{aligned} p-1 \equiv (-1)^1 \mod p \\ 2 \equiv (-1)^2 \mod p \\ p-3 \equiv (-1)^3 \mod p \\ \cdots (\frac{2}{p}) \equiv 2^{\frac{p-1}{2}} \equiv (-1)^{\frac{p^2-1}{8}} \;\mod p \end{aligned}$

证毕。

定理 8：(Gauss 二次互反律) 设 $p,q$ 为不同的奇素数，则有

$(\frac{p}{q}) (\frac{q}{p}) = (-1)^{\frac{(p-1)(q-1)}{4}}$

证明太长了，下次一定吧 0.0

Jacobi 符号

Jacobi 符号的引入只是为了让计算更加简洁！

我们在计算用 Gauss 二次互反律求 $(\frac{a}{q})$ 时，由于 $a$ 要因式分解成很多项，所以直接用不是很方便。因此我们引入 Jacobi 符号:

设 $Q = q_1 \cdots q_s$ 是正奇数，其中 $q_1 \leq \cdots \leq q_s$ 是奇素数（手算时候可以保证严格小于），我们定义：

$(\frac{a}{Q}) = (\frac{a}{q_1}) \cdots (\frac{1}{q_s})$

$Q$ 为奇素数时，Jacobi 符号就是 Legendre 符号
$(\frac{a}{Q}) = 1$ 并不等价于 $x^2 \equiv a \mod Q$ 有解！
$(\frac{a}{Q})$ 是 $a$ 的可乘函数，周期为 $Q$ 的周期函数
当 $(a,Q)>1$ 时，$(\frac{a}{Q})=0$
当 $(a,Q)= 1$ 时，$(\frac{a^2}{Q})=1$；特别地，$(\frac{1}{Q}) = 1$
$(\frac{-1}{Q}) = (-1)^{\frac{Q-1}{2}}$
$(\frac{2}{Q}) = (-1)^{\frac{Q^2-1}{8}}$
$(\frac{P}{Q}) = (-1)^{\frac{(P-1)(Q-1)}{4}} (\frac{Q}{P})$，其中 $P,Q$ 都是正奇数。
写程序计算时可以避免做质因数分解！！！

注意到 Jacobi 符号只是为了简化 Legendre 符号的计算的！

计算例子

判断二次同余式 $x^2 \equiv 888 \mod 1999$ 是否有解。

$\begin{aligned} (\frac{888}{1999}) &= (\frac{4}{1999}) (\frac{2}{1999}) (\frac{111}{1999}) \\ &= (-1) ^{\frac{1999^2 -1}{8}} (\frac{111}{1999}) \\ &= (-1)^{\frac{(1999-1)(111-1)}{4}} (\frac{1999}{111}) \\ &= -(\frac{1}{111}) = -1 \end{aligned}$

如果取模的数不是素数，那么就把它分解素因数，然后每个单独判断即可。

Jacobi 符号 Python 程序

import math
# a是整数，Q是正奇数
def Jacobi(a,Q):
	# print(a,Q)  # 需要看过程就取消本行最前面的注释
	a%=Q
	if math.gcd(a,Q) > 1:  return 0
	while a%4==0: a//=4
	f = lambda n:1-2*(n&1)
	ans = 1
	if a%2==0: a//=2;ans = f((Q**2-1)//8)
	# 此时a也是正奇数了
	if a == 1:  return ans
	return ans*f((a-1)*(Q-1)//4)*Jacobi(Q,a)

print(Jacobi(888,1999))