二次非剩余

数论基本概念

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

定义

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

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

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

研究二次剩余的理论称为二次剩余理论。二次剩余理论在实际上有广泛的应用，包括从噪音工程学到密码学以及大数分解。

研究历史以及基本概念

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

基本结论

质数二次非剩余

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

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

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

（0计算在内）

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

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

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

合数二次非剩余

首先可以看出，

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

比如，对于模15的情况

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

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