二次剩余与勒让德符号

二次同余看起来只是 $x^2 \equiv a \pmod p$，真正要先回答的却是：这个平方在模 $p$ 下存不存在。根可以以后再找（Cipolla 或 Tonelli–Shanks），判别本身已经够用一套完整的语言：二次剩余、勒让德符号、欧拉准则，再加二次互反律把计算压到手算能做完的规模。

二次剩余在说什么

设 $p$ 是奇素数，$a$ 是整数。方程

要么无解，要么恰有两个互相反数的解（$p \mid a$ 时只有零解 $x \equiv 0$）。

当 $p \nmid a$ 且方程有解时，称 $a$ 是模 $p$ 的二次剩余；无解则称二次非剩余。$p \mid a$ 时，$a$ 与 $p$ 不互素，通常不把它算进「剩余 / 非剩余」这两类，只说方程有平凡解 。

解若存在，必成对出现。若 $x_0^2 \equiv a$，则 $(-x_0)^2 \equiv a$，且 为奇素数时 。反过来，同一个剩余不会对应超过这两个根：若 ，则 ，只能是 。所以「有解」和「恰有两解」在 时是同一件事。

模 $7$ 看一遍就清楚。$1^2,2^2,3^2$ 分别同余 $1,4,2$，再往后 $$、、，只是重复。所以模 的二次剩余是 ，非剩余是 。一半一半，不是巧合：乘法群 是循环群，平方映射的核是 ，像的大小恰好是 。

同余可以像等式那样乘，但「两边开方」没有一般法则。$x^2 \equiv 2 \pmod 7$ 有解，$x^2 \equiv 3 \pmod 7$ 没有，不能从「 比 大」读出任何信息。一次同余里 的存在性由 一锤定音；二次同余没有这么短的算术条件，必须另造判别式。

勒让德符号

把「剩不剩余」收成一个取值只有 $0,\pm 1$ 的记号，就是勒让德符号。对奇素数 $p$ 和整数 $a$，

于是 $x^2 \equiv a \pmod p$ 有解，当且仅当 $\bigl(\frac{a}{p}\bigr) \neq -1$。符号为 时有且仅有零解；为 时恰有两解。若只要「能不能开方」，看符号是否为 即可；若还要根的个数，把 和 分开。

同余类相同则符号相同：$\bigl(\frac{a}{p}\bigr)=\bigl(\frac{a \bmod p}{p}\bigr)$。手算第一步永远是把底数收进 ，再分解质因数。不要对一个比 还大的合数直接互反。

它是完全积性的：

所以 $\bigl(\frac{a^2}{p}\bigr)=1$（只要 $p \nmid a$），$($。负数先拆出 ：

$2$ 也有闭式，不必枚举：

这两条加上积性，已经能消掉符号里的 $-1$ 和 $2$。剩下的奇数底数，交给互反律。记忆时可以分开：模 $4$ 管 $-1$，模 $8$ 管 $2$，互反管两个奇素数谁换谁。三条各管一块，不要混用。

欧拉判别法

勒让德符号的定义依赖「有没有平方根」，直接用定义等于枚举，模一大就没意义。欧拉准则把它变成一次幂运算：

右边在模 $p$ 下只可能是 $0$、$1$ 或 $p-1$。最后一种就是 $-1$。于是：

• $p \mid a$ 时两边都是 $0$；
• 否则费马小定理给出 $a^{p-1}\equiv 1$，所以 $a^{(p-1)/2}\equiv \pm 1$，正负恰好对应剩余与非剩余。

为什么对得上？设 $g$ 是模 $p$ 的一个原根，$a \equiv g^k$。$a$ 是平方当且仅当 $k$ 为偶数，而

$k$ 偶则 $1$，$k$ 奇则 $-1$。这就是欧拉准则。不必真的找出原根：存在性由有限域理论保证，计算时只做模幂。

手算时指数可以先模 $p-1$（费马），再快速幂。$p$ 很小时，列出 $1^2,\dots,\bigl(\frac{p-1}{2}\bigr)^2$ 往往更快，因为后一半平方只是重复。欧拉准则的价值在模数变大之后：枚举要 次乘法，模幂只要 次。

它给出判别，不给出根。$a^{(p-1)/2}\equiv 1$ 只告诉你平方根存在，并不构造出 $x$。想把 $x$ 找出来，需要 Tonelli–Shanks 或 Cipolla，那是另一篇文章的事。

二次互反律

欧拉准则的指数是 $(p-1)/2$，模 $p=10^9+7$ 这类数时计算机毫无压力，纸上算 $a^{5\cdot 10^8}$ 就不现实。二次互反律把 和 绑在一起，让两个素数可以交换位置。

设 $p,q$ 是不相等的奇素数。则

右边只取决于 $p,q$ 模 $4$ 的类：

• 若 $p,q$ 中至少有一个 $\equiv 1 \pmod 4$，则 $\bigl(\frac{p}{q}\bigr)=\bigl(\frac{q}{p}\bigr)$；

完整证明（高斯引理、格点计数，或圆上的高斯和）篇幅不短，这里略去。高斯引理把 $\bigl(\frac{a}{p}\bigr)$ 写成一串最小绝对剩余的符号乘积，再数格子就能看到互反两边差一个 $(-1)$ 的指数；高斯和则把同样的符号嵌进单位根的平方和。知道名字即可，手算用的是结论。

用法比证明更常被问起：把较大的素数降到较小的模上，再拆因子、消 $2$、必要时再互反，直到底数变成 $1$。每次互反都要先看两个素数模 $4$ 是否都是 $3$，漏掉改号是最常见的笔误。

高斯和的补充形式也常用。对奇数 $n>0$，

右边的 $\bigl(\frac{p}{n}\bigr)$ 已不是勒让德而是雅可比符号，但当 $n$ 本身是素数时两者重合。手算时只要记住：先把底数收进 $[0,p)$，再分解。

纸上可以固定成四步，不容易漏号：

1. 取模，使 $0 \le a < p$。若 $a=0$，符号为 $0$，停。
2. 写出 $a$ 的素因子分解，积性拆成若干 $\bigl(\frac{q}{p}\bigr)$，负数先拆 。

这和下面递推代码是同一条路，只是人按质因数拆，机器按除以 $2$ 和取模走。

手算例子

例一：欧拉准则直接判

问 $3$ 是不是模 $7$ 的二次剩余。$(7-1)/2=3$，

故 $\bigl(\frac{3}{7}\bigr)=-1$，无解。对照前面的枚举：$1,2,4$ 里没有 $3$。

再看 $2$ 模 $7$：$2^3=8\equiv 1$，所以 $\bigl(\frac{2}{7}\bigr)=1$。的确 。用 的闭式验一次：，符号应为 ，一致。

例二：互反律降模

计算 $\bigl(\frac{5}{17}\bigr)$。$5$ 和 $17$ 都是 $\equiv 1 \pmod 4$，互反不改号：

$5\equiv -3 \pmod 8$，故 $\bigl(\frac{2}{5}\bigr)=-1$。于是 无解。

若不用互反，欧拉准则要算 $5^8 \bmod 17$。也能做：$5^2=25\equiv 8$，$5^4\equiv 64\equiv 13$，，同一答案，只是步数更多。

例三：先拆因子再互反

计算 $\bigl(\frac{15}{17}\bigr)$。$15=3\cdot 5$，

例二已经得到后者为 $-1$。前者：$3\equiv 3\pmod 4$，$17\equiv 1\pmod 4$，互反不改号，

$3\equiv 3\pmod 8$，故 $\bigl(\frac{2}{3}\bigr)=-1$。两个因子都是 ，乘积为 。所以 是模 的二次剩余。

谁是根？从小到大试：$1^2,\dots,7^2$ 同余 $1,4,9,16,8,2,15$。果然 $7^2=49$，另一个根是 。判别只保证存在，根仍要另找——模很小就枚举，模很大才需要 Tonelli–Shanks。

例四：带负号

$\bigl(\frac{-3}{13}\bigr)$。先拆 $-1$：$13\equiv 1\pmod 4$，故 。再算 。两者都 ？，，仍不改号：

所以 $\bigl(\frac{-3}{13}\bigr)=1$。验算：$4^2=16\equiv 3$，则 对应……不对， 说明 是剩余，，应看 。，确实有解。负数务必先处理符号，不要把 直接拿去和 互反——互反律要求两个正奇素数。

例五：两个素数都是 $3 \bmod 4$

计算 $\bigl(\frac{7}{19}\bigr)$。$7$ 和 $19$ 都 $\equiv 3 \pmod 4$，互反要改号：

$5\equiv 1\pmod 4$，$7\equiv 3\pmod 4$，这一步不改号：

于是 $\bigl(\frac{7}{19}\bigr)=-(-1)=1$。$8^2=64\equiv 7 \pmod{19}$，另一个根是 。若第一下忘了改号，会得到 ，和验算对不上。

欧拉准则交叉验证：$(19-1)/2=9$，$7^2=49\equiv 11$，$7^4\equiv 121\equiv 7$，，故 ，同为 。

例六：较大底数先取模

问 $100$ 是不是模 $31$ 的二次剩余。先取模：$100\equiv 7 \pmod{31}$，故 $\bigl(\frac{100}{31}\bigr)=\bigl(\frac{7}{31}\bigr)$。两者都 ，改号：

$3$ 与 $7$ 也都 $\equiv 3 \pmod 4$，再改一次号：

所以有解。$100=10^2$，当然是剩余——这个例子用来提醒：底数本身是平方时，只要 $p \nmid a$，符号必为 $1$，取模后的 $7$ 看起来「不像平方」，互反仍会回到 $1$。写程序时不必先判断「是不是完全平方」，准则自己会处理。

一份可直接用的实现

欧拉准则最短，适合确认单个符号。快速幂是 $O(\log p)$ 次乘法。模数保证是素数时，它比递推更不容易写错：没有互反改号，也没有抽因子 $2$。代价是指数大，手算不合适，机器无所谓。

pow 的三参数形式就是模幂。返回值已经是 $0,\pm 1$，不要把 $p-1$ 留在外面。

互反律可以写成递推，避免大指数，也更接近手算顺序：不断把底数模掉、抽出因子 $2$、交换两个奇数。下面同时给出雅可比符号——当模数是奇素数时它就是勒让德。

递推版每一步把问题缩小，复杂度仍是 $O(\log^2 n)$ 量级的位运算，和欧几里得同一数量级。竞赛里模数已经保证是素数时，两份代码应当给出相同答案；不一致就回头检查「$p-1$ 有没有当成 $-1$」或「交换时有没有漏掉两个 $3 \bmod 4$」。

递推过程可以对照例五。求 $\bigl(\frac{7}{19}\bigr)$：两者都是奇数，先交换并因 $7\equiv 19\equiv 3\pmod 4$ 改号，变成 ；再交换（不改号）得 ；抽出 ， 再改一次号，得到 。和手算同一条路，只是循环代替了纸上的箭头。

jacobi 对合数模也有定义，但 $\bigl(\frac{a}{n}\bigr)=1$ 不蕴含 $x^2\equiv a\pmod n$ 有解。雅可比是勒让德按素因子的乘积：若 ，则

即使乘积为 $1$，也可能每个因子都是 $-1$ 而个数为偶，整体「看起来像剩余」，局部却无解。例如 $\bigl(\frac{2}{15}\bigr)=\bigl(\frac{2}{3}\bigr)\bigl(\frac{2}{5}\bigr)=(-1)(-1)=1$，而 与 都无解，更不必说模 。要判合数模，应拆成素因子幂再对每个素因子用勒让德（必要时再用亨泽尔提升），不能只看雅可比。

Solovay–Strassen 素性测试正是利用这一点：随机抽 $a$，比较 $a^{(n-1)/2}$ 与雅可比符号。合数上两者容易不一致，素数上欧拉准则强制相等。写符号函数时若模数可能是合数，返回值的含义要在注释里写清。

写代码时容易踩的坑

先取模再算。$a$ 为负时，Python 的 % 会收成 $[0,p)$，欧拉准则和递推都能接着用。若语言里负余数保持负号，必须自己先规范化，否则 $\bigl(\frac{-3}{13}\bigr)$ 会走错分支。

欧拉准则的输出在 $\{0,1,p-1\}$ 里，不是 $\{0,\pm 1\}$。漏掉 p-1 → -1 这一步，后面当乘法因子用就会把符号乘飞。

互反律的前提是两个不相等的奇素数。底数是 $1$、$2$ 或偶数时不要互反，先用闭式或拆 $2$。$p=q$ 时符号是 $0$，不是去套公式。

$\bigl(\frac{2}{p}\bigr)$ 看的是模 $8$，不是模 $4$。$p\equiv 3\pmod 4$ 只决定 ，不决定 。 且 ， 而 。

积性是乘性的，不是加性的。$\bigl(\frac{a+b}{p}\bigr)$ 与 $\bigl(\frac{a}{p}\bigr)+\bigl(\frac{b}{p}\bigr)$ 没有关系。例三里 ，但 ，不能拆成两个符号相加。

勒让德等于 $1$ 只说明存在平方根，代码若接着「随便开方」会得到浮点误差。整数解要枚举、或走 Tonelli–Shanks / Cipolla。模 $2$ 是退化情形：$x^2\equiv a\pmod 2$ 对 $a\equiv 0,1$ 都有解，多数实现直接特判。

合数模上「剩不剩余」不能只用一个符号。中国剩余定理把问题拆开：对每个 $p^k$ 有解，整体才有解。$p^k$ 上从模 $p$ 的解往上抬，是亨泽尔引理，条件是导数 $2x$ 在该素因子处可逆，也就是奇素数上的非零根都能抬。$p=2$ 的高次幂要单独处理， 已有额外限制， 才可能继续往 抬。

和开平方算法的边界

判别解决「有没有」，开平方解决「是谁」。素数模上的标准算法是 Tonelli–Shanks：先把 $p-1$ 写成 $2^s\cdot q$（$q$ 奇），再在 $2$-西罗子群里调整。Cipolla 则在 $\mathbb{F}_{p^2}$ 里取一个模 的非剩余构造二次扩张。两者都以勒让德符号为前置：没有剩余就直接停，有剩余才进入开方。

一次同余提供求逆和中国剩余定理，二次剩余提供存在性。合在一起，才能把 $x^2\equiv a\pmod m$ 在一般模上拆开、抬上去。更高次剩余要原根和指标，那是离散对数一侧的语言。

所以不必把勒让德符号看成竞赛里的冷门公式。它是二次同余的开关：先用欧拉或互反把 $\pm 1$ 算对，再决定要不要去找根。手算走互反，代码走模幂，两套答案应当咬合。把存在性、符号计算和开平方三件事分开，这一层就不会和一次同余搅在一起。