二次剩余

来自吾萌百科

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