概论
求解一元高阶同余方程思路
-
分解模数为素数幂相乘 $$m=p_{1}^{c_{1}}p_{2}^{c_{2}}\dots p_{k}^{c_{k}}$$
-
解模为素数幂的同余方程 $$f(x)\equiv 0 \ \mathrm{mod}, p_{i}^{c_{i}}$$
-
解模为素数的同余方程 $$f(x)\equiv 0 \ \mathrm{mod},p$$
-
用 中国剩余定理 合并解 $$\left{ x \equiv b_{i} \ \mathrm{mod},p_{i}^{c_{i}} \right} \Rightarrow x \equiv b \ \mathrm{mod},m $$
素数幂模降阶
已知
- $f(a)\equiv0 \ \mathrm{mod} , p^{k}$
- 令 $\lambda := \frac{f(a)}{p^{k}}$
则
-
升阶解 $f(x)\equiv0 \ \mathrm{mod} , p^{k+1}$ 具有形式 $$x\equiv a+t\cdot p^{k} \ \mathrm{mod},p^{k+1}$$
- 若 $f’(a) \neq 0 \ \mathrm{mod},p$ $\Rightarrow$ 唯一解 $t$
- 若 $f’(a)\equiv0 \ \mathrm{mod},p$ 且 $\lambda \neq0$ $\Rightarrow$ 无解
- 若 $f’(a)\equiv 0 \ \mathrm{mod},p$ 且 $\lambda\equiv 0$ $\Rightarrow$ $t=0,1,\dots,p-1$ 共 $p$ 个解
素数模高阶方程
解
$$ f(x)\equiv 0 \ \mathrm{mod},p $$
- 【去高阶】用 $x^{p-1}\equiv 1 \ \mathrm{mod},p$ 简化 $f(x)$，使得 $\mathrm{deg},f<p$
- 【穷举根】用试根法因式分解 $g(x)$ 求得解 注意灵活运用系数取模以及加减模同余