二次剩余
二次剩余
模 
的二次剩余
我们只需研究形如 )
的同余方程即可.
当 
时，（3）仅有一个解 
. 所以下面我们总假定 
.
如果同余方程(3)有解，则称 
是模 的二次剩余（在不引起混淆时，简称为二次剩余）；否则称 时模 的二次非剩余（简称二次非剩余）
如果同余方程（3）有解，则同余方程（3）恰有两个解. 此外，若 是二次剩余，则模 同余类 
中每个数都是二次剩余. 对于二次非剩余也是如此.
Legendre符号
对每个整数 ，定义
%3D%5Cbegin%7Bcases%7D%201%2C%26%E5%A6%82%E6%9E%9C%20a%E6%98%AF%E6%A8%A1p%E7%9A%84%E4%BA%8C%E6%AC%A1%E5%89%A9%E4%BD%99%2C%5C%5C%20-1%2C%26%E5%A6%82%E6%9E%9Ca%E6%98%AF%E6%A8%A1p%E7%9A%84%E4%BA%8C%E6%AC%A1%E9%9D%9E%E5%89%A9%E4%BD%99%2C%5C%5C%200%2C%26%E5%A6%82%E6%9E%9C%20p%7Ca.%20%5Cend%7Bcases%7D)
定理1
设 时奇素数，则模 的任意完系中恰有 
个二次剩余，以及 个二次非剩余；并且模 的全部二次剩余在
%5E2)
所属的模 的同余类中.
定理2
设 为素数，则模 的两个二次剩余之积时二次剩余，模 的一个二次剩余和一个而二次非剩余之积是而此非剩余，模 的两个二次非剩余之积是二次非剩余，模 的两个而此非剩余之积是二次剩余。
定理3（欧拉判别法则）
设 为奇素数，则
%5Cequiv%20a%5E%7B%5Cfrac%7Bp-1%7D%7B2%7D%7D%5Cpmod%7Bp%7D)
推论1
设 为奇素数，则
%3D(-1)%5E%7B%5Cfrac%7Bp-1%7D%7B2%7D%7D%3D%5Cbegin%7Bcases%7D%201%2C%26%5Ctext%7Bif%7D%5C%3B%5C%3Bp%5Cequiv1%5Cpmod%7B4%7D%5C%5C%20-1%2C%26%5Ctext%7Bif%7D%5C%3B%5C%3Bp%5Cequiv3%5Cpmod%7B4%7D%20%5Cend%7Bcases%7D)
推论2
设 为奇素数，则
%3D(-1)%5E%7B%5Cfrac%7Bp%5E2-1%7D%7B8%7D%7D%3D%5Cbegin%7Bcases%7D%201%2C%26%5Ctext%7Bif%7D%5C%3B%5C%3Bp%5Cequiv%5Cpm1%5Cpmod%7B8%7D%5C%5C%20-1%2C%26%5Ctext%7Bif%7D%5C%3B%5C%3Bp%5Cequiv%5Cpm3%5Cpmod%7B8%7D%20%5Cend%7Bcases%7D)
整数与多项式-【目录】
