二次剩余

在 模同余公理库模同余Congruence modulo n两整数之差被给定正整数整除时成立的等价关系。意义下，平方剩余是平方映射能够到达的类。是否为平方取决于模数，不能从整数本身的正负或大小判断。Legendre 符号把这个可达性问题压成一个数：非零平方记 $1$，非平方记 $-1$。

平方为什么恰占一半 ​

若 $x^2\equiv y^2(\mathrm{mod}p)$，则 $p\mid (x-y)(x+y)$。素数性保证 $p\mid x-y$ 或 $p\mid x+y$，所以同一个平方的原像只有 $x$ 与 $-x$。对非零 $x$，这两个类又不同：否则 $p\mid 2x$，与 $p$ 为奇素数且 $p\nmid x$ 矛盾。于是 $p-1$ 个非零类恰好两两配对，给出 $(p-1)/2$ 个不同平方，也证明了每个非零平方恰有两个根。

Euler 判据为什么能识别这两半 ​

写 $h=(p-1)/2$。若 $a=x^2$ 是非零平方，费马小定理公理库费马小定理Fermat's little theorem素数 p 与不被 p 整除的整数 a 满足 a^(p−1)≡1 mod p。给出

因此全部 $h$ 个非零平方都是多项式 $T^h-1$ 的根。素数域上非零 $h$ 次多项式公理库多项式环Polynomial ring系数来自给定环、以形式不定元构造的多项式集合。至多有 $h$ 个根：每找到一个根就能除去一个一次因子，且非零元素可以消去，逐次降低次数即可证明这个根数界。已知的平方已经占满根的位置，非平方便不可能满足 $a^h\equiv 1$。

另一方面，对任意非零 $a$，费马小定理仍给出 $(a^h{)}^2\equiv 1$。因 $p$ 为素数，$(a^h-1)(a^h+1)\equiv 0$ 迫使 $a^h\equiv 1$ 或 $-1$。非平方只能取后一种值，Euler 判据就此得证；当 $p\mid a$ 时，判据两边都为零。

完全乘法性也随之得到。由 $(ab{)}^h=a^h{b}^h$，有

非零情形下两边只取 $1,-1$，而它们在奇素数模下不同，所以同余就是符号的相等；若有一个因子被 $p$ 整除，两边同为零。这说明两个非剩余的积反而是剩余，却没有给加法提供同样的规则。

模 $7$ 的非零平方为 $1,2,4$，所以 $\left(\frac{2}{7}\right)=1$、$\left(\frac{3}{7}\right)=-1$。只需算 $1^2,2^2,3^2$：其余三个非零类分别是它们的相反数，不会产生新的平方。

考察 $-1$ 是否为平方，可以直接看出模数对结论的控制。模 $13$ 时

所以 $-1$ 是二次剩余；模 $11$ 的非零平方只有 $1,3,4,5,9$，其中没有 $-1\equiv 10$。一般地，对奇素数 $p$，Euler 判别给出

故 $-1$ 为二次剩余当且仅当 $p\equiv 1(\mathrm{mod}4)$。零类必须单独处理：$0$ 确实是平方，却不属于通常所说的“非零二次剩余”，Legendre 符号也因此把它记为 $0$ 而不是 $1$。

从判定存在到算出平方根 ​

当 $p\equiv 3(\mathrm{mod}4)$ 且 $a$ 是非零二次剩余时，指数 $(p+1)/4$ 是整数，可以直接取

因为 Euler 判据给出 $a^{(p-1)/2}\equiv 1$，所以

例如 $p=11,a=3$，先算 $3^5=243\equiv 1(\mathrm{mod}11)$，确认它是剩余；再算 $r=3^3=27\equiv 5$。两根为 $5,6$，代回得到 $25\equiv 36\equiv 3(\mathrm{mod}11)$。二次互反律公理库二次互反律Law of quadratic reciprocity把两个不同奇素数互为二次剩余的符号用一个精确的互反公式联系起来。提供另一条判定 $3$ 为剩余的路线，而这里的幂公式完成了实际求根。

公式有两个实质条件：若 $p\equiv 1(\mathrm{mod}4)$，该指数不是整数；若 $a$ 为非剩余，则同一计算得到 $r^2\equiv -a$，不会解出原方程。零的平方根则只有零，无需使用此公式。

合数模数下，局部平方必须全部通过 ​

模 $15$ 的 $1$ 有四个平方根：$1,4,11,14$。它们模 $3$、模 $5$ 的余数依次为 $(1,1),(1,-1),(-1,1),(-1,-1)$。中国剩余定理公理库整数中国剩余定理Chinese remainder theorem for integers用最大公因数判定一般联立同余的相容性，并构造模最小公倍数唯一的解。把每对符号唯一拼成一个模 $15$ 的类；四个符号组合说明根既不少也不多。这也解释了为什么“非零平方恰有两个根”必须保留奇素数条件。

合数模数还有一个容易误判的例子。Jacobi 符号将正奇数模数分解为素因子，按重数相乘相应的 Legendre 符号，因此

可是模 $3$ 的平方只有 $0,1$，$x^2\equiv 2(\mathrm{mod}3)$ 无解，故模 $15$ 的原方程也无解。乘积为 $1$ 可以来自两个负号；要求每个局部条件可解，比只检查这个乘积更强。

计算二次同余时，可以把工作分成三步：先用 Euler 判据或互反律判断素数模下是否有根，再在适用条件下构造根，最后用 CRT 拼接互素模数的局部根。判定、求根与拼接各自回答不同的问题，前面的 $3(\mathrm{mod}11)$ 与 $1(\mathrm{mod}15)$ 正好展示了这三步。

进入有限域公理库有限域Finite field · Galois field底层集合有限的域。后，平方判断还能帮助选择商域模型：模 $3$ 的 $-1=2$ 不是平方，故二次多项式 $t^2+1$ 没有根、从而不可约。把它的根记作 $\alpha$，便得到可实际计算的 ${\mathbb{F}}_9$ 模型；其中关系 ${\alpha }^2=-1$ 接替了整数模数，负责把乘法结果约回两个系数。

若继续求模 ${11}^2,{11}^3,\dots$ 的平方根，Hensel 引理公理库Hensel 引理：简单根的唯一提升Hensel's lemma · 亨泽尔引理模素数的简单根在指定余类内唯一提升为 p-adic 根，并以逐位递推计算 11-adic 的三的平方根。提供另一种推进方式：$T^2-3$ 在 $5,6$ 处的导数模 $11$ 都非零，所以两根各自唯一提升。模 ${11}^5$ 的两根是 $26042,135009$；这种逐位提高同一素数的精度，与用 CRT 拼接不同素数的条件分属两个步骤。