无编辑摘要 |
无编辑摘要 |
||
| 第1行： | 第1行： | ||
对于方程<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>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> 。 | 而当 <math>n \equiv 0 \pmod p</math> 的情况，也就是<math>n \mid p</math> ，这种情况下 <math>n</math> 既不是 <math>QR</math> 也不是 <math>NR</math> 。 | ||
== QR与NR的乘法法则 == | == QR与NR的乘法法则 == | ||
2024年2月16日 (五) 09:49的最新版本
对于方程[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]