二次剩余和Gauss互反律

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

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

二次剩余

考虑如下形式二次同余式

其中 $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 符号

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

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

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

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

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

证毕。

推论2 (Wilson 定理)

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

推论3 (Euler 判别法)

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

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

推论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:

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

证毕。

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

太长了,下次一定吧0.0

Jacobi 符号

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

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

设$Q = q_1 \cdots q_s$是正奇数,其中$q_1 \leq \cdots \leq 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{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$ 是否有解。

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

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))
如有帮助,烦请资瓷(一块也是爱0.0)