二次剩余

数学术语

二次剩余是数论基本概念之一。它是初等数论中非常重要的结果，不仅可用来判断二次同余式是否有解，还有很多用途。C.F.高斯称它为算术中的宝石，他一人先后给出多个证明。

定义

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

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

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

几个自然数

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

历史及概念

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

设P是奇素数，且(p,a)=1,二次同余方程的一般形式是

ax2+bx+c≡0(modp). (4-1)

由(p,a)=1知(p,4a)=1,所以(4-1)式和同余方程

4a(ax2+bx+c)≡0(mod p)的解相同，上式可写为

(2ax+b)2≡b2-4ac(mod p). (4-2)

容易看出，通过变量替换

y≡2ax +b(mod p) (4-3)

同余方程(4-2)与同余方程

y≡b2-4ac(mod p) (4-4)

是等价的。也就是说，两者同时有解或无解，有解时，对(4-4)式的每个解y≡ y0(modp)通过(4-3)式给出(4-2)式的一个解x≡xo(modp),由(4-4)式的不同的解给出(4-2)式的不同的解，反过来也对。此外，两者的解数相同。由以上的分析得出，我们只要讨论形如

x2≡n(mod p) (4-5)

的同余方程即可。当p|n时，(4-5)式仅有一解

x≡0(mod p).

所以，以后恒假定(p,n)=1.我们知道p是奇素数，且当(n,P)=1时，同余方程x2≡n(modp)要么无解，要么有偶数个关于模p的不同余的解为确定同余方程x2≡n(modp)的解的存在性问题，我们引人二次剩余的概念。

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

基本结论

质数二次剩余

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

以下讨论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时，所有的奇数的平方分别是：

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

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

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

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

当k

合数二次剩余

首先可以看出，

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

比如，对于模15的情况

1, 2, 3,4, 5,6, 7, 8,9,10, 11, 12, 13, 14（粗斜体为二次剩余）。

两个二次非剩余2和8的乘积是二次剩余1，但另外两个二次非剩余2和7的乘积是二次非剩余14。