对于方程[math]\displaystyle{ x^2 \equiv n \pmod p }[/math]，若对于奇素数 [math]\displaystyle{ p }[/math] 和满足 [math]\displaystyle{ n \nmid p }[/math] 的整数 [math]\displaystyle{ n }[/math]，该方程的 [math]\displaystyle{ x }[/math] 有整数解，则我们称 [math]\displaystyle{ n }[/math] 是关于模 [math]\displaystyle{ p }[/math] 的二次剩余，记做 [math]\displaystyle{ QR }[/math] 。而对于无整数解的称呼其为模 [math]\displaystyle{ p }[/math] 的二次非剩余。记做 [math]\displaystyle{ NR }[/math]。
而当 [math]\displaystyle{ n \equiv 0 \pmod p }[/math] 的情况，也就是 [math]\displaystyle{ n \mid p }[/math] ，这种情况下 [math]\displaystyle{ n }[/math] 既不是 [math]\displaystyle{ QR }[/math] 也不是 [math]\displaystyle{ NR }[/math] 。
QR与NR的乘法法则
对于 [math]\displaystyle{ QR }[/math] 和 [math]\displaystyle{ NR }[/math] ,我们有如下性质。
性质一：[math]\displaystyle{ QR \times QR=QR }[/math]
性质二：[math]\displaystyle{ QR \times NR=NR }[/math]
性质三：[math]\displaystyle{ NR \times NR=QR }[/math]
性质四：[math]\displaystyle{ NR \times QR=NR }[/math]
性质与 [math]\displaystyle{ 1 }[/math] 和 [math]\displaystyle{ -1 }[/math] 之间的性质很像，所以我们可以设 $[math]\displaystyle{ QR=1 }[/math]，[math]\displaystyle{ NR=-1 }[/math]
legendre 符号
对于 [math]\displaystyle{ QR }[/math] 与 [math]\displaystyle{ NR }[/math] ，我们可以定义 [math]\displaystyle{ legendre }[/math] 符号。
[math]\displaystyle{ \left(\frac{n}{p} \right)= \begin{cases} 1& \text{Is QR of mod p}\\ -1& \text{Is NR of mod p} \end{cases} }[/math]
设 [math]\displaystyle{ p }[/math] 为奇素数，则 [math]\displaystyle{ \left(\frac{a}{p} \right)\left(\frac{b}{p} \right) = \left(\frac{ab}{p} \right) }[/math]
欧拉准则
[math]\displaystyle{ \left(\frac{n}{p} \right)\equiv n^{\frac{p-1}{2}} \pmod p }[/math]