二次剩余是数论基本概念之一，它是初等数论中非常重要的结果。
什么是二次剩余呢？简单来说就是如果存在一个整数$x$，使得$x^2≡n(mod p)$，那么则称$n$是模$p$的二次剩余。
有一种很巧妙的办法，可以得出一个数是否是模$p$的二次剩余。这个办法是勒让德符号$(frac{n}{p})$。 如果$n$是模$p$的二次剩余，那么$(frac{n}{p})=1$；
如果$n$不是模$p$的二次剩余，那么$(frac{n}{p})=-1$；
如果$p|n$，则$(frac{n}{p})=0$ 这里有一个结论：$(frac{n}{p})=n^{frac{p-1}{2}}$ （前提是$p$是奇质数） 证明：（不看也无所谓）
①如果$n$是模$p$的二次剩余，那么$sqrt n$与$p$互质，那么根据费马小定理$(sqrt n)^{p-1}≡1(mod p)$。
②如果$n$不是模$p$的二次剩余，那么因为$p$是奇质数，所以根据扩欧可知对于$i∈[1,p-1]$，都有一个$j∈[1,p-1]$使其满足$ij≡n(mod p)$。所以我们可以把$1,2……p-1$分成$frac{p-1}{2}$对，每对的乘积在模$p$下都是$n$，那么$(p-1)!≡n^{frac{p-1}{2}}(mod p)$，根据威尔逊定理有$(p-1)!≡-1(mod p)$，所以$n^{frac{p-1}{2}}≡-1(mod p)$
③如果$p|n$，那么显然$n^{frac{p-1}{2}}≡0(mod p)$

定理：对于方程$x^2≡n(mod p)$，有$frac{p-1}{2}$个不同的$n$,使得该方程有解。

证明：若有两个数$u$和$v$均满足它们的平方在$p$时同余，那么必然有$p|(u+v)(u−v)$。由于$p$不可能整除$u−v$，那么可以得出$p$整除$u+v$。这个结论反过来也是成立的，因此共有$frac{p-1}{2}$种不同的平方。且每一个$p$的二次剩余恰好有两个解。 那么怎么求一个二次剩余呢？我们可以按照下面的方法: 在$[0,p-1]$随机挑选一个数，称其为$a$，定义$w=a^2-n$，若$(frac{w}{p})=-1$，那么$(a+sqrt w)^{frac{p+1}{2}}$就是一组二次剩余。 证明：$(a+sqrt w)^{p}=sum_{i=0}^{p}(C_{p}^{i}a^{p-i})(C_{p}^{p-i}(sqrt w)^{i})$