二次剩余和 Gauss 互反律

最后更新于:2022年6月25日 下午

从二次剩余问题,引入 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 程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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))