|
本帖最后由 zytsang 于 2021-8-2 00:07 编辑
有 \(\gcd(4a,n)\ne1\),可令 \(4a=4=4\times1=a_1\times a_2\)
原方程变为求解
\[y^2\equiv 84 \equiv 4 \pmod{80}\implies y\equiv\{2,18,22,38,42,58,62,78\}\pmod{80}\]
第二步可稍作简化:
\[2x\equiv y-4 \pmod{80}\implies x\equiv \frac{y-4}{2} \pmod{40}\]
取所有y值代入
\[y=2\implies x\equiv -1 \equiv 39 \pmod{40}\implies x\equiv19\pmod{20}\]
\[y=18\implies x \equiv 7 \pmod{40}\implies x\equiv7\pmod{20}\]
\[y=22\implies x \equiv 9 \pmod{40}\implies x\equiv9\pmod{20}\]
\[y=38\implies x \equiv 17 \pmod{40}\implies x\equiv17\pmod{20}\]
\[y=42\implies x \equiv 19 \pmod{40}\implies x\equiv19\pmod{20}\]
\[y=58\implies x \equiv 27 \pmod{40}\implies x\equiv7\pmod{20}\]
\[y=62\implies x \equiv 29 \pmod{40}\implies x\equiv9\pmod{20}\]
\[y=78\implies x \equiv 37 \pmod{40}\implies x\equiv17\pmod{20}\]
可得原方程的所有解:
\[x\equiv \{7,9,17,19\}\pmod{20}\]
|
|