二次同余方程
| 二次同余方程 | |
|---|---|
| 术语名称 | 二次同余方程 |
| 英语名称 | quadratic congruence |
二次同余方程(quadratic congruence)指形如 [math]\displaystyle{ ax^2 + bx + c \equiv 0 \pmod n }[/math] 的同余方程。其中左侧是未知数的最高次数为 2 的整式。
定义
对正整数 [math]\displaystyle{ n }[/math] 和整数 [math]\displaystyle{ a, b, c }[/math] ，且 [math]\displaystyle{ n \not\mid a }[/math] ，形如 [math]\displaystyle{ ax^2 + bx + c \equiv 0 \pmod n }[/math] 的方程称为二次同余方程(quadratic congruence)。
若 [math]\displaystyle{ (\exists x_0 \in \mathbb{Z})(ax_0^2 + bx_0 + c \equiv 0 \pmod n) }[/math] ，则称 [math]\displaystyle{ x \equiv x_0 \pmod n }[/math] 为二次同余方程 [math]\displaystyle{ ax^2 + bx + c \equiv 0 \pmod n }[/math] 的解。
解
模为 2 的情况
此时 x 只分为同余于 0 和同余于 1 两种情况，简单讨论，或者说考虑奇偶性即可得到结果。
模为奇质数的情况
由于 [math]\displaystyle{ \operatorname{gcd}(4a, p) = 1 }[/math] ，二次同余方程可被配方为
[math]\displaystyle{ (2ax + b)^2 \equiv b^2 - 4ac \pmod {p} }[/math]
因此，这一一般的二次同余方程可以被拆解为一个二项二次同余方程和一个一次同余方程：
[math]\displaystyle{ \begin{cases} y^2 \equiv \Delta \pmod{p} \\ 2ax + b \equiv y \pmod{p} \\ \end{cases} }[/math]
有解条件
由于 [math]\displaystyle{ \operatorname{gcd}(2a, p) = 1 }[/math] ，以上一次同余方程 [math]\displaystyle{ x }[/math] 与 [math]\displaystyle{ y }[/math] 的解是一一对应的，因此解数和以上二项二次同余方程相同。
为解决是否有解问题，需要知道是否有，这里引入概念二次剩余，并通过计算勒让德符号确定，而这一符号又通常借助雅可比符号计算。
如果 [math]\displaystyle{ \left( \Delta\over p \right) = 1 }[/math] ，则二项二次同余方程有两解，此时 [math]\displaystyle{ y }[/math] 有两解，则 [math]\displaystyle{ x }[/math] 也有两解；如果 [math]\displaystyle{ \left( \Delta\over p \right) = 0 }[/math] ，即 [math]\displaystyle{ p | \Delta }[/math] ，则二项二次同余方程有解 [math]\displaystyle{ y \equiv 0 \pmod p }[/math] ，此时 [math]\displaystyle{ x }[/math] 也对应有一解；如果 [math]\displaystyle{ \left( \Delta\over p \right) = -1 }[/math] ，则二项二次同余方程无解，此时 [math]\displaystyle{ y }[/math] 无解，则 [math]\displaystyle{ x }[/math] 也无解。
解法
根据以上论述，可以先计算 [math]\displaystyle{ \Delta \equiv b^2 - 4ac \pmod p }[/math] 的模 [math]\displaystyle{ p }[/math] 的平方根，再通过一次同余方程的解法得到 [math]\displaystyle{ x }[/math] 的解。
模为质数幂的情况
此处内容待补充。
模为一般合数的情况
此处内容待补充。
类似地，由于此时无法保证互质，乘以 [math]\displaystyle{ 4a }[/math] 时方程的模数也要同样操作才能保证解相同，最终方程化为
[math]\displaystyle{ \begin{cases} y^2 \equiv \Delta \pmod{4am} \\ 2ax + b \equiv y \pmod{4am} \\ \end{cases} }[/math]
结合模数拆成互质时有双射中国剩余定理，可以先分开解模数是质数幂的情况，然后按分别的同余关系映射回一般的模数。