二次互反律

两个素数互相作为平方模数时并不是彼此独立的问题。二次互反律把“$p$ 是否是模 $q$ 的平方”与反向问题精确联系起来，差别只由 $p,q$ 模 $4$ 的类别控制：按 模同余公理库模同余Congruence modulo n两整数之差被给定正整数整除时成立的等价关系。分类，只要至少一个素数同余于 $1(\mathrm{mod}4)$，交换分子与分母便保持符号；只有两者都同余于 $3(\mathrm{mod}4)$ 时符号才反转。于是原本需要逐个试平方的局部问题，可以沿取余过程不断把数字降小，变成类似 Euclidean 算法的递归判定。

判断 $3$ 是否为模 $11$ 平方：二者都为 $3(\mathrm{mod}4)$，故

因此 $3$ 是模 $11$ 的二次剩余。此处还能把存在性落实为具体答案：因为 $11\equiv 3(\mathrm{mod}4)$，用二次剩余页的求根公式公理库二次剩余Quadratic residue模奇素数同余于某个平方的非零剩余类。得 $3^{(11+1)/4}=3^3\equiv 5(\mathrm{mod}11)$，另一根是 $-5\equiv 6$。验算 $5^2\equiv 6^2\equiv 3(\mathrm{mod}11)$，就把互反判定与求根计算接起来了。

主公式要求不同奇素数；分子含 $-1$ 或 $2$ 时需补充定律，分子合数时先因式分解并用乘法性。若 $p=q$，Legendre 符号为零，不适用互反公式。高次剩余存在更复杂的互反律，不能直接套用同一符号规则。

判断 $13$ 是否为模 $47$ 的二次剩余。因为 $13\equiv 1(\mathrm{mod}4)$，交换分子与分母不产生负号：

又因 $13\equiv 5(\mathrm{mod}8)$，补充定律给出 $(2/13)=-1$，故最终结果为 $-1$；方程 $x^2\equiv 13(\mathrm{mod}47)$ 无解。整个计算只经过取余、互反与 $2$ 的补充定律，避免了枚举二十多个平方。互反律判定的是根是否存在，并不直接构造根；结果为 $1$ 时仍需另用模平方根算法找到具体解。

二次剩余公理库二次剩余Quadratic residue模奇素数同余于某个平方的非零剩余类。的 Legendre 符号经互反律可沿 Euclidean 算法公理库整数欧几里得算法Euclidean algorithm for integers反复使用带余除法计算最大公约数的有限算法。式递归快速计算，从而高效判定二次同余是否可解。它支撑平方同余求解、素数在二次域中的分解、Gauss 和与若干密码构造，并成为高次互反律和现代代数数论的原型。