形式陈述

设 $p$$p$ 为奇素数，且 $a\not\equiv0\pmod p$$a\not\equiv 0(\mathrm{mod}p)$。若存在 $x$$x$ 使

$$ x^2\equiv a\pmod p, $$$$x^2\equiv a(\mathrm{mod}p),$$

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

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

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

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

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

直觉

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

例子与边界

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

推论与应用

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

参考资料

• 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。