求解 x^2 ≡ a (mod n)
本帖最后由 uk702 于 2023-1-5 12:51 编辑当n为素数 p 时，华罗庚的《数论导引》中给出了如下的解答（下面用 (a, p) 表示勒让德符号 \( \left( \frac{a}{p} \right) \)）：
1）若 \(p\equiv 3\pmod{4}\)，由于有 (a, p) = 1，故 \( a^{\frac{p-1}{2}} \equiv 1 \pmod{p}\)，∴\( (a^{\frac{p+1}{4}})^2 \equiv a\pmod{p} \)
∴\( a^{\frac{p+1}{4}} \) 为其解。
2）若 \(p\equiv 5\pmod{8}\)，先求 a = -1 的解，由威尔逊定理，有 \( -1\equiv (p-1)! \equiv (1 \cdot 2 \cdot 3 ... \cdot \frac{p-1}{2})^2\equiv \left( \frac{p-1}{2}! \right)^2 \)
∴\( (\frac{p-1}{2})! \) 是 \( x^2 \equiv -1 \pmod{p}\) 的解。
对于一般的 \( x^2 \equiva\pmod{p}\)，由于有 (a, p) = 1，故 \( a^{\frac{p-1}{2}} \equiv 1\pmod{p}\)，计算得 \( \left( a^{\frac{p+3}{8}} \cdot \frac{p-1}{2} ! \right)^2\equiv a \pmod{p}\)
∴ \( a^{\frac{p+3}{8}} \cdot\left( \frac{p-1}{2} \right)! \)是它的解。
3）若 \(p\equiv 1\pmod{8}\)，书云无太好的解法，一般可采取逐步舍弃的方法，详见书。
http://www.numbertheory.org/calc/krm_calc.html，提供若干工具（函数），用以求解这类问题（和各种类型的二元二次丢番都不定方程），
如求解 x^2+3 ≡ 0 (mod 9999999967)，可用 sqroot(-3, 9999999967, &a[])，解得 x=±831463263 。
另，如果用 MMA 或 Pari/GP，如何求解？我看了一下 guide/NumberTheory，还没找到明显的答案。 PowerModList[-3, 1/2, 9999999967]
Solve https://www.math.canterbury.ac.nz/~j.booher/expos/sqr_qnr.pdf \(p\equiv3\pmod{4}\)和\(p\equiv1\pmod{4}\)两种类型进行，其中\(p\equiv1\pmod{4}\)见如下链接：
https://bbs.emath.ac.cn/forum.php?mod=viewthread&tid=15803&page=1#pid78100
另见《数论经典著作系列:初等数论(3)》陈景润
页:
[1]