查看“︁二次同余方程”︁的源代码

[[分类:同余方程]]
{{InfoBox
|name=二次同余方程
|eng_name=quadratic congruence
}}
'''二次同余方程'''('''quadratic congruence''')指形如 <math>ax^2 + bx + c \equiv 0 \pmod n</math> 的[[同余方程]]。其中左侧是未知数的最高[[次数]]为 2 的[[整式]]。

== 定义 ==

对正整数 <math>n</math> 和整数 <math>a, b, c</math> ，且 <math>n \not\mid a</math> ，形如 <math>ax^2 + bx + c \equiv 0 \pmod n</math> 的方程称为'''二次同余方程'''('''quadratic congruence''')。

若 <math>(\exists x_0 \in \mathbb{Z})(ax_0^2 + bx_0 + c \equiv 0 \pmod n)</math> ，则称 <math>x \equiv x_0 \pmod n</math> 为'''二次同余方程 <math>ax^2 + bx + c \equiv 0 \pmod n</math> 的解'''。

== 解 ==

=== 模为 2 的情况 ===

此时 x 只分为同余于 0 和同余于 1 两种情况，简单讨论，或者说考虑奇偶性即可得到结果。

=== 模为奇质数的情况 ===

由于 <math>\operatorname{gcd}(4a, p) = 1</math> ，二次同余方程可被配方为

<math> (2ax + b)^2 \equiv b^2 - 4ac \pmod {p}</math>

因此，这一一般的二次同余方程可以被拆解为一个二项二次同余方程和一个[[一次同余方程]]：

<math>
\begin{cases}
y^2 \equiv \Delta \pmod{p} \\
2ax + b \equiv y \pmod{p} \\
\end{cases}
</math>

==== 有解条件 ====

由于 <math>\operatorname{gcd}(2a, p) = 1</math> ，以上一次同余方程 <math>x</math> 与 <math>y</math> 的解是一一对应的，因此解数和以上二项二次同余方程相同。

为解决是否有解问题，需要知道是否有，这里引入概念[[二次剩余]]，并通过计算 [[Legendre 符号]]确定，而这一符号又通常借助 [[Jacobi 符号]]计算。

如果 <math>\left( \Delta\over p \right) = 1</math> ，则二项二次同余方程有两解，此时 <math>y</math> 有两解，则 <math>x</math> 也有两解；如果 <math>\left( \Delta\over p \right) = 0</math> ，即 <math>p | \Delta</math> ，则二项二次同余方程有解 <math>y \equiv 0 \pmod p</math> ，此时 <math>x</math> 也对应有一解；如果 <math>\left( \Delta\over p \right) = -1</math> ，则二项二次同余方程无解，此时 <math>y</math> 无解，则 <math>x</math> 也无解。

==== 解法 ====

根据以上论述，可以先计算 <math>\Delta \equiv b^2 - 4ac \pmod p</math> 的模 <math>p</math> 的平方根，再通过一次同余方程的解法得到  <math>x</math> 的解。

=== 模为质数幂的情况 ===

{{待补充}}

=== 模为一般合数的情况 ===

{{待补充}}

类似地，由于此时无法保证互质，乘以 <math>4a</math> 时方程的模数也要同样操作才能保证解相同，最终方程化为

<math>
\begin{cases}
y^2 \equiv \Delta \pmod{4am} \\
2ax + b \equiv y \pmod{4am} \\
\end{cases}
</math>

结合模数拆成互质时有双射[[中国剩余定理]]，可以先分开解模数是质数幂的情况，然后按分别的同余关系映射回一般的模数。


{{同余理论}}