勒让德符号

1. 定义

设 $p$ 是奇素数， $a$ 是任意整数。勒让德符号 $(\frac{a}{p})$ 定义如下：

(\frac{a}{p}) = ⎩ ⎨ ⎧ 1, - 1, 0, 若 a 是模 p 的平方剩余 (QR) 若 a 是模 p 的平方非剩余 (QNR) 若 p ∣ a

该符号的值与欧拉判别法的结果在模 $p$ 下同余： $(\frac{a}{p}) \equiv a^{\frac{p - 1}{2}} (mod p)$

为了快速计算 $(\frac{a}{p})$ 的值，通常利用以下性质而不是直接定义：

同余性 (Periodicity)：若 $a \equiv b (mod p)$ ，则 $(\frac{a}{p}) = (\frac{b}{p})$ 。 用途：将大整数 $a$ 转化为小于 $p$ 的整数。
完全积性 (Multiplicativity)： $(\frac{ab}{p}) = (\frac{a}{p}) (\frac{b}{p})$ 用途：将合数分解为素因子乘积，分别计算。
平方数：若 $(k, p) = 1$ ，则 $(\frac{k ^{2}}{p}) = 1$ 。

记忆以下两个关键公式，用于处理分解后的因子 $- 1$ 和 $2$ ：

对 $- 1$ 的判定： $(\frac{- 1}{p}) = (- 1)^{\frac{p - 1}{2}} = {1, - 1, p \equiv 1 (mod 4) p \equiv 3 (mod 4)$
对 $2$ 的判定： $(\frac{2}{p}) = (- 1)^{\frac{p ^{2} - 1}{8}} = {1, - 1, p \equiv \pm 1 (mod 8) p \equiv \pm 3 (mod 8)$

这是计算的核心加速器。设 $p, q$ 是不同的奇素数： $(\frac{q}{p}) = (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} (\frac{p}{q})$

计算口诀

“两奇同余三，互换变负号”：只有当 $p$ 和 $q$ 模 $4$ 都余 $3$ 时，互换位置后符号改变（乘以 $- 1$ ）。

“否则符号不变”：其他情况（至少有一个模 $4$ 余 $1$ ），直接互换位置，符号不变。

题目：判断 $286$ 是否为模 $563$ 的平方剩余（已知 $563$ 是素数）。

解：

分解分子： $286 = 2 \times 11 \times 13$ 。 $(\frac{286}{563}) = (\frac{2}{563}) (\frac{11}{563}) (\frac{13}{563})$ 。
计算 $(\frac{2}{563})$ ： $563 \equiv 3 (mod 8)$ （因为 $560$ 是 $8$ 的倍数），根据性质 $(\frac{2}{p})$ ，结果为 $- 1$ 。
计算 $(\frac{13}{563})$ ： $13 \equiv 1 (mod 4)$ ，互换不变号。 $(\frac{13}{563}) = (\frac{563}{13}) = (\frac{4}{13}) = 1$ （ $4$ 是平方数）。
计算 $(\frac{11}{563})$ ： $11 \equiv 3 (mod 4)$ 且 $563 \equiv 3 (mod 4)$ ，互换变号。 $(\frac{11}{563}) = - (\frac{563}{11}) = - (\frac{2}{11})$ 。 $11 \equiv 3 (mod 8)$ ，故 $(\frac{2}{11}) = - 1$ 。所以这一项结果为 $- (- 1) = 1$ 。
汇总： $(\frac{286}{563}) = (- 1) \times 1 \times 1 = - 1$ 。结论： $286$ 是模 $563$ 的平方非剩余。