求解 x^2 ≡ a (mod n)

uk702

当  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 \equiv  a\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，还没找到明显的答案。

wayne

1. PowerModList[-3, 1/2, 9999999967]

复制代码

1. Solve[x^2 + 3 == 0, Modulus -> 9999999967]

复制代码

mathe

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.ph ... amp;page=1#pid78100
另见《数论经典著作系列:初等数论(3)》陈景润