二次剩余

下表列出了1至25对2至25的二次剩余。

从17世纪到18世纪，费马、欧拉、拉格朗日和勒让德等数论学家对二次剩余理论作了初步的研究，证明了一些定理^[1]并作出了一些相关的猜想^[2]，但首先对二次剩余进行有系统的研究的数学家是高斯。他在著作《算术研究》（Disquisitiones Arithmeticae，1801年）中首次引入了术语“二次剩余”与“二次非剩余”，并声明在不至于导致混淆的行文中，可以省略“二次”两字。

为了得到关于一个整数${\displaystyle n}$ 的所有二次剩余（在一个完全剩余系中），我们可以直接计算0, 1,…, n − 1的平方模${\displaystyle n}$ 的余数。但只要注意到a² ≡(n − a)²(mod n)，我们就可以减少一半的计算量，只算到n/2了。于是，关于${\displaystyle n}$ 的二次剩余的个数不可能超过n/2 + 1（n为偶数）或(n + 1)/2（n为奇数）^[3]。

两个二次剩余的乘积必然还是二次剩余。

质数二次剩余

对于质数2，每个整数都是它的二次剩余。

以下讨论${\displaystyle p}$ 是奇质数的情况：

对于${\displaystyle X}$ ，${\displaystyle X^{2}\equiv d{\pmod {p}}}$ 而言，能满足“${\displaystyle d}$ 是模${\displaystyle p}$ 的二次剩余”的${\displaystyle d}$ 共有${\displaystyle {\frac {(p+1)}{2}}}$ 个（剩余类），分别为：

${\displaystyle 0^{2},1^{2},...\left({{\frac {(p-1)}{2}}-1}\right)^{2},\left({\frac {p-1}{2}}\right)^{2}}$ （0计算在内）

此外是${\displaystyle {\frac {(p-1)}{2}}}$ 个二次非剩余。但在很多情况下，我们只考虑乘法群Z/pZ，因此不将0包括在内。^[4]这样，每个二次剩余的乘法逆元仍然是二次剩余；二次非剩余的乘法逆元仍然是二次非剩余。^[5]二次剩余的个数与二次非剩余的个数相等，都是${\displaystyle {\frac {(p-1)}{2}}}$ 。^[4]此外，两个二次非剩余的乘积是二次剩余，二次剩余和二次非剩余的乘积是二次非剩余。^[5]

应用二次互反律可以知道，当${\displaystyle p}$ 模4余1时，-1是${\displaystyle p}$ 的二次剩余；如果${\displaystyle p}$ 模4余3，那么，-1是${\displaystyle p}$ 的二次非剩余。

要知道d是否为模p的二次剩余，可以运用欧拉判别法（或叫欧拉准则）。

质数乘方的二次剩余

每个奇数的平方都模8余1，因此模4也余1。设a是一个奇数。m为8，16或2的更高次方，那么a是关于m的二次剩余当且仅当a ≡ 1(mod 8)^[6]。

比如说，在模32时，所有的奇数的平方分别是：

1² ≡ 15² ≡ 1

3² ≡ 13² ≡ 9

5² ≡ 11² ≡ 25

7² ≡ 9² ≡ 17

模8都余1。而偶数的二次剩余是：

0² ≡ 8² ≡ 16² ≡ 0

2² ≡ 6²≡ 10² ≡ 14²≡ 4

4² ≡ 12² ≡ 16

可以看出，关于8，16或2的更高次方的二次剩余是具有4^k(8n + 1)形式的所有数，其中${\displaystyle k}$ 、${\displaystyle n}$ 为整数。

对于奇质数${\displaystyle p}$ 以及与${\displaystyle p}$  互质的整数${\displaystyle A}$ ，${\displaystyle A}$ 是关于${\displaystyle p}$ 的若干次乘方的剩余当且仅当它是关于${\displaystyle p}$ 的剩余。

设模的是pⁿ（n次乘方），

那么p^kA

当k ≥ n时是模pⁿ的剩余；

当k < n并为奇数时是模pⁿ的非剩余。

当k < n并为偶数时，

如果${\displaystyle A}$ 是关于${\displaystyle p}$ 的剩余，那么p^kA就是模pⁿ的剩余；

如果${\displaystyle A}$ 是关于${\displaystyle p}$ 的非剩余，那么p^kA就是模pⁿ的非剩余^[7]。

合数二次剩余

首先可以看出，

如果a是模n的剩余，并且p^k 整除n，那么a是模p^k的剩余。

如果a是模n的非剩余，那么存在p^k 整除n，使得a是模p^k的非剩余。

对于模合数的情况，两个剩余的乘积仍然是剩余，剩余和非剩余的乘积必为非剩余，但是两个非剩余的乘积则可能是剩余、非剩余或0。

比如，对于模15的情况
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14（粗斜体为二次剩余）。
两个二次非剩余2和8的乘积是二次剩余1，但另外两个二次非剩余2和7的乘积是二次非剩余14。

高斯使用^[8]R和N来分别表示二次剩余及二次非剩余。例如：2 R 7，5 N 7，并且1 R 8，3,5,7 N 8。尽管这种记号在某些方面来说十分简洁^[9][10]，但现今最常用的是勒让德符号，或称二次特征（见狄利克雷特征）。对于整数a及奇质数p，

${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}\;\;\,0\\+1\\-1\end{cases}}}$	如果p整除a；
	如果a是模p的二次剩余且p不整除a
	如果a是模p的二次非剩余。

之所以将0另分一类有两个原因。首先，这使公式和定理叙述方便。其次，二次特征是一个从乘法群Z/pZ射到复数域的群同态，${\displaystyle ({\tfrac {np}{p}})=0}$ 可以将这个同态扩张到整数构成的乘法半群^[11]。

相比高斯的记号，勒让德符号的优势在于可以写在公式里（作为一个数字值）。此外勒让德符号可以推广到三次以至高次剩余。

勒让德符号中的分母只限奇质数，对于一般的奇合数，有推广的雅可比符号。雅可比符号的性质比前者复杂。如果a R m那么${\displaystyle ({\tfrac {a}{m}})=1}$ ，如果${\displaystyle ({\tfrac {a}{m}})=-1}$ 那么a N m。但如果${\displaystyle ({\tfrac {a}{m}})=1}$ ，我们不能知道a R m还是a N m。

二次剩余的推广叫做高次剩余，是研究任意${\displaystyle X}$ ，${\displaystyle X^{n}\equiv d{\pmod {p}}}$ 中${\displaystyle d}$ 是否为模${\displaystyle p}$ 的${\displaystyle n}$ 次剩余的问题。

• 勒让德符号
• 同余
• 欧拉准则
• 二次互反律
• 三次互反律

• 闵嗣鹤、严士健，《初等数论》，第二版，高等教育出版社，2001年。

• 李宗儒，高斯二次互反律^{[永久失效链接]}