二次剩余 | Codeboy's Blog

形式陈述

设 $p$ 为奇素数，且 $a\not\equiv0\pmod p$ 。若存在 $x$ 使

x^2\equiv a\pmod p,

则称 $a$ 为模 $p$ 的二次剩余，否则为二次非剩余。Legendre 符号定义为

\left(\frac ap\right)= \begin{cases} 0,&p\mid a,\\ 1,&a\text{ 为非零二次剩余},\\ -1,&a\text{ 为二次非剩余}. \end{cases}

它对分子完全乘法，并由 Euler 判据刻画：

a^{(p-1)/2}\equiv\left(\frac ap\right)\pmod p.

模 $p$ 的 $p-1$ 个非零类中恰有 $(p-1)/2$ 个二次剩余，每个有两个平方根。

直觉

平方映射在非零有限域乘法群上把 $x$ 与 $-x$ 合并为同一值，因此像恰占一半；Legendre 符号把是否落在该像中编码成 $\pm1$ 。

在模同余意义下，模 $n$ 的二次剩余是平方映射能够到达的剩余类。对奇素数 $p$ ，非零平方把乘法群中的元素成对识别为 $x$ 与 $-x$ ，因此恰有 $(p-1)/2$ 个非零二次剩余。是否为平方取决于模数，不能从整数本身的正负或大小判断。

例子与边界

模 $7$ 的非零平方为 $1,2,4$ ，所以 $\left(\frac27\right)=1$ 、 $\left(\frac37\right)=-1$ 。定义中的 $p$ 必须是奇素数；合数模下 Jacobi 符号虽形式相似，但值 $1$ 不保证为平方。零类单独赋值零。若 $a$ 是剩余，其两个根为 $x$ 与 $-x$ ，在奇素数模下不同。二次剩余性只依赖 $a\bmod p$ 。Legendre 符号的乘法性不意味着它对加法有简单规律。

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

5^2=25\equiv-1\pmod{13},

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

\left(\frac{-1}{p}\right)=(-1)^{(p-1)/2},

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

推论与应用

二次剩余连接有限域平方、二次同余、素数分布、密码协议和二次互反律。

Legendre 符号编码素模下的二次剩余性，二次互反律高效交换分子分母。在有限域上，平方剩余用于求模平方根；它还进入 Blum 整数密码假设、二次域分解和 Gauss 和。

参考资料

Kenneth Ireland and Michael Rosen, A Classical Introduction to Modern Number Theory, 2nd ed., Springer, 1990，Ch. 5, quadratic residues, Legendre symbol, and Euler criterion。
Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., Wiley, 1991，Ch. 3, quadratic congruences and Legendre symbol。

形式陈述 ​

反向链接

形式陈述