[科普中国]-二次剩余

定义

在数论中，特别在同余理论里，一个整数X对另一个整数p的二次剩余（英语：Quadratic residue）指X的平方除以p得到的余数。

当存在某个X，式子 成立时，称**“d是模p的二次剩余”**

当对任意不成立时，称**“ d是模 p的二次非剩余”**

几个自然数下表列出了1至25对2至25的二次剩余。

|| || 二次剩余列表

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

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

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

基本结论质数二次剩余对于质数2，每个整数都是它的二次剩余。3

以下讨论p是奇质数的情况：

对于X， 而言，能满足“d是模 p的二次剩余”的 d共有 个（剩余类），分别为：

（0计算在内）

此外是 个二次非剩余。但在很多情况下，我们只考虑乘法群Z/pZ，因此不将0包括在内。这样，每个二次剩余的乘法逆元仍然是二次剩余；二次非剩余的乘法逆元仍然是二次非剩余。二次剩余的个数与二次非剩余的个数相等，都是。此外，两个二次非剩余的乘积是二次剩余，二次剩余和二次非剩余的乘积是二次非剩余。

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

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

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

比如说，在模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(8n+ 1)形式的所有数，其中k、n为整数。

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

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

那么pA

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

当k