初等数论入门 Lesson 8 二次剩余与二次互反律

二次剩余

Quadratic Residue

$p$ 为奇素数，且 $p\not\mid a$ 给定

$$x^2\equiv a \pmod p$$

若 $x$ 存在，则称 $a$ 是模 $p$ 的二次剩余（QR），否则是二次非剩余（QNR）

勒让德符号

Lengendre 符号

定义：

$$\left(\frac{a}{p}\right)= \begin{cases} 1, & p\nmid a \text{ 且 } a \text{ 是模 } p \text{ 的二次剩余} \\ -1, & p\nmid a \text{ 且 } a \text{ 是模 } p \text{ 的二次非剩余} \\ 0, & p\mid a \end{cases}$$

满足以下性质：

• 周期性 / 可模约：

  $$\left(\frac{a}{p}\right) = \left(\frac{a \bmod p}{p}\right)$$

• 完全积性

  $$\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$$

欧拉判别法

Euler’s Criterion

$$\boxed{\left(\dfrac a p\right)\equiv a^{\frac {p-1}2}\pmod p}$$

由费马小定理：

$$a^{p-1}\equiv 1\pmod p$$

因此 $a^{\frac {p-1}2}$ 只能是1或-1.

高斯引理

$$\left(\frac a p\right)=(-1)^n,\;n=\{ka\}_{k=1}^{(p-1/2)}中>\frac p 2的个数$$

二次互反律

若 $p,q$ 为两个不同的奇素数，则：

$$\left(\frac p q\right)\left(\frac q p\right)=(-1)^{\frac {p-1}2\cdot\frac{q-1}2}$$

雅克比符号

Jocobi 符号

性质：

• 完全积性

• 周期性

• 互反律

• -1的符号：

  $$\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} = \begin{cases} 1, & p \equiv 1 \pmod{4} \\ -1, & p \equiv 3 \pmod{4} \end{cases}$$

• 2的符号：

  $$\left(\frac 2 p\right)=(-1)^{\frac{p^2-1}8}$$

  即 $p\equiv \pm 1\pmod 8$ 得 $1$，$p\equiv \pm 3\pmod 8$ 得 $-1$

只要利用周期性+互反律+完全积性+（-1）与2的符号，就可以计算出大量的雅可比符号了。

二次同余方程求解

求解：

$$x^2 \equiv a \pmod{p}$$

情况1：

若 $p \equiv 3 \pmod{4}$ 且 $\left(\dfrac{a}{p}\right) = 1$，则

$$x \equiv \pm a^{\frac{p+1}{4}} \pmod{p}$$

情况2：$p\equiv 1\pmod 4$

用Tonelli-Shanks算法求解