查看“二次剩余”的源代码

对于方程<math>x^2 \equiv n \pmod p</math>，若对于奇素数 <math>p</math> 和满足 <math>n \nmid p</math> 的整数 <math>n</math>，该方程的 <math>x</math> 有整数解，则我们称 <math>n</math> 是关于模 <math>p</math> 的二次剩余，记做 <math>QR</math> 。而对于无整数解的称呼其为模 <math>p</math> 的二次非剩余。记做 <math>NR</math>。

而当 <math>n \equiv 0 \pmod p</math> 的情况，也就是 <math>n \mid p</math> ，这种情况下 <math>n</math> 既不是 <math>QR</math> 也不是 <math>NR</math> 。

== QR与NR的乘法法则 ==
对于 <math>QR</math> 和 <math>NR</math> ,我们有如下性质。

性质一：<math>QR \times QR=QR</math>

性质二：<math>QR \times NR=NR</math>

性质三：<math>NR \times NR=QR</math>

性质四：<math>NR \times QR=NR</math>

性质与 <math>1</math> 和 <math>-1</math> 之间的性质很像，所以我们可以设 $<math>QR=1</math>，<math>NR=-1</math>

== legendre 符号 ==
对于 <math>QR</math> 与 <math>NR</math> ，我们可以定义 <math>legendre</math> 符号。

<math>
\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>p</math> 为奇素数，则 <math>\left(\frac{a}{p} \right)\left(\frac{b}{p} \right) = \left(\frac{ab}{p} \right)</math>

== 欧拉准则 ==
<math>
\left(\frac{n}{p} \right)\equiv n^{\frac{p-1}{2}} \pmod p
</math>

[[Category:数学]]