二次剩余

对于方程[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]