二次剩余和Gauss互反律

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

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

二次剩余

考虑如下形式二次同余式

其中 $p$ 是奇素数,$a$是非负整数。若上述方程有解,则称$a$是$p$ 的二次剩余,记作$a\; R\; p$;否则称$a$是$p$ 的二次非剩余,记作$a \; \overline{R}\; p$ 。

经过简单推理很容易发现,在模 $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

欧尼酱,人家想喝可乐!