|
|
本帖最后由 青青子衿 于 2021-12-11 16:06 编辑 针对素数模的二次同余方程（其解被称为模\(\,p\,\)余\(\,a\,\)的平方根）
\[\large\boxed{x^2\equiv a\pmod{p}}\]
当素数\(\,p\,\)为\(\,4n+1\,\)时，作如下讨论
设素数\(\,p=4n+1\,\),\(\,n=2^\lambda\cdot\!s\,\),其中\(\,u\,\)为奇数，\(\lambda\ge0\);
记\(\,a\,\)是模\(\,p\,\)的平方剩余（即存在一个整数\(\,x_0\,\)使得\(\,{x_0}^2\equiv a \pmod{p}\,\)）;
记\(\,b\,\)是模\(\,p\,\)的平方非剩余（即对任意一个整数\(\,x_{a}\,\)都有\(\,{x_a}^2\not\equiv a \pmod{p}\,\)）;
故素数\(\,p\,\)可以写为
\[\,p=4\cdot2^\lambda\cdot\!s+1\,\]
1)若有\(\,a^s\equiv1\pmod{p}\,\)或\(\,a^s\equiv-1\pmod{p}\,\)
那么\(\,x^2\equiv a\pmod{p}\,\)的解为
\[x\equiv\pm a^{\frac{s+1}{2}}\pmod{p}\]
或
\[x\equiv\pm a^{\frac{s+1}{2}}b^n\pmod{p}\]
2)若有\(\,a^s\not\equiv\pm1\pmod{p}\,\)
那么在\(\,1,2,\cdots,2^\lambda-1\,\)这些数中，必有一数\(\,h\,\)，它能够使得
\[\left(b^{2s}\right)^h\equiv-a^s\pmod{p}\]
或
\[\left(b^{2s}\right)^h\equiv+a^s\pmod{p}\]
则\(\,x^2\equiv a\pmod{p}\,\)的解为
\[x\equiv\pm a^{\frac{s+1}{2}}b^{n-hs}\pmod{p}\]
或
\[x\equiv\pm a^{\frac{s+1}{2}}b^{2n-hs}\pmod{p}\]
\[
\boxed{
\begin{align*}
\text{
引理\(\quad\)当\(\quad a^s\not\equiv\pm1\pmod{p}\quad\)时，则必有一正整数\(\,\mu<\lambda\,\)，它能使得\(\qquad\)
}\\
\hspace{5cm}
\left(a^s\right)^{2^\mu}\equiv-1\pmod{p}\hspace{5cm}\\
\text{
\(\,\qquad\)则此时必有一奇数\(\,t\,\)（其中\(\,0\leqslant t\leqslant 2^\mu-1\,\)），使得\(\,\,{\color{brown}{h=2^{\lambda-\mu}\cdot\!t}}\,\,\)能满足\(\quad\)
}\\
\hspace{5cm}
\left(b^{2s}\right)^h\equiv-a^s\pmod{p}\hspace{5cm}\\
\end{align*}
}
\]
参考《数论经典著作系列:初等数论(3)》陈景润 |
|
hbghlyj
发表于 2023-2-27 18:35
