模二次方程有解的充要条件

设 $f(x) = ax^2+bx+c$, 在域 $\mathbb{Z} / p \mathbb{Z}$ 中何时有根。我们不妨只考虑 $0<a<p$ 的情形。因为
$$ 4af(x) = (2ax+b)^2 - (b^2-4ac) $$
因此我们设 $d = b^2-4ac$,显然可知 $f(x)$ 有根当且仅当 $d$ 是模 $p$ 二次剩余。至于求解也是很简单的事。

一个小推广

$f(x,y) = ax^2+bxy+cy^2=0$ 显然有解 $(x,y)=(0,0)$ 。那么何时有非平凡解呢?其实非平方解等价于说 $x,y$ 在域 $\mathbb{F}_p$ 中可逆,因此又回到上面单变量的情形了。

虽然问题很简单,但是具体实现的时候会有很多trick。例如 $a=0,d=0,p=2$ 这些都是需要特判的。

写这么短的博文确实0.0