Legendre 符号

为了简洁地表示二次剩余和二次非剩余，我们可以引入模奇素数$p$的 Legendre 符号。

定义

对于奇素数$p$以及任意整数$a$，称$a$对$p$的 Legendre 符号是$\left(\dfrac{a}{p}\right)$，它的值定义为

1. 若$p \nmid a$且$a$是模$p$的二次剩余，则值为$1$；
2. 若$p \nmid a$且$a$是模$p$的二次非剩余，则值为$-1$；
3. 若$p \mid a$，则值为$0$。

显然，$\left(\dfrac{0}{p}\right) = 0, \left(\dfrac{1}{p}\right) = 1.$

性质

1. 完全积性函数，即$\forall a, b \in \Z, \left(\dfrac{ab}{p}\right) = \left(\dfrac{a}{p}\right) \left(\dfrac{b}{p}\right)$；
2. 若$a \equiv b \pmod{p}$，则$\left(\dfrac{a}{p}\right) = \left(\dfrac{b}{p}\right)$，特别地，$\left(\dfrac{a}{p}\right) = \left(\dfrac{a+kp}{p}\right), \forall k \in \Z$；
3. $\left(\dfrac{d^2}{p}\right) = 1$；
4. 二次同余方程$x^2 \equiv a \pmod{m}$模$m$的解数（不计重数）为$1 + \left(\dfrac{a}{p}\right)$。

由于 Legendre 符号的完全积性，我们只需把握$\left(\dfrac{-1}{p}\right), \left(\dfrac{2}{p}\right), \left(\dfrac{q}{p}\right)$，$q$为素数的 Legendre 符号值就可把握任意$m$的 Legendre 符号值。

Euler 判别法则

$\left(\dfrac{d}{p}\right) \equiv d^{\frac{p-1}{2}} \pmod{p}$，特别地，$\left(\dfrac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} = \begin{cases} 1, & p \equiv 1 \pmod{4}; \\ -1, & p \equiv -1 \pmod{4}. \end{cases}$

这给出了 Legendre 符号在$-1$处的值，下面我们讨论在$2$处的值。

Gauss 引理

设$p$为奇素数，$(a, p) = 1$，记$r = \dfrac{p-1}{2}$，令$\mu$是$a, 2a, \cdots, ra$当中模$p$的最小正剩余大于$\dfrac{p}{2}$的个数，则$\left(\dfrac{a}{p}\right) = (-1)^\mu.$

特别地，当$a=2$时，$\left(\dfrac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}} = \begin{cases} 1, p \equiv \pm 1 \pmod{8}; \\ -1, p \equiv \pm 3 \pmod{8}. \end{cases}.$

二次互反律

为了计算两个奇素数的 Legendre 符号而引入的，它可以将不宜求解的较大的数的 Legendre 符号不断缩小。它的形式是 设$p,q$为两个奇素数，则有
$\left( \frac{p}{q} \right)\left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}} = \begin{cases} 1, p \equiv 1 \pmod{4} \text{ or } q \equiv 1 \pmod{4}; \\ -1, p \equiv q \equiv 3 \pmod{4}. \end{cases}.$

上下节

• 上一节：二次剩余
• 下一节：二次互反律