二次剩余和 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: $ -() (p-1)! a^{} p $

Proof: 对于 \(p \mid a\) 的情形，结论显然。下面考虑 \((p,a)=1\) 的情形，令 \[ S = \lbrace 1,2,\cdots,p-1 \rbrace \] 对任意的 $ x S $ 必存在唯一的 $ y S $ 为下面同余式的解

\[ yx \equiv a \; \mod p \]

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

当 $ () = 1 $ 时，同余式 $ x^2 = a ; 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：$() =()() $

推论 6 说明，我们求 Legendre 符号，只需求 $ (),() $ 即可

定理 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))