|
|
当 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，还没找到明显的答案。 |
|
发表于 2023-10-3 08:15:38
