概论
求解一元高阶同余方程思路
- 分解模数为素数幂相乘 $$m=p_{1}^{c_{1}}p_{2}^{c_{2}}\dots p_{k}^{c_{k}}$$
- 解模为素数幂的同余方程 $$f(x)\equiv 0 \ \mathrm{mod}, p_{i}^{c_{i}}$$
- 用 中国剩余定理 合并解 $$\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$ 个解