高阶同余方程

概论

求解一元高阶同余方程思路

分解模数为素数幂相乘 $$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$$
用中国剩余定理 CRT 合并解 $$\left{ x \equiv b_{i} \ \mathrm{mod},p_{i}^{c_{i}} \right} \Rightarrow x \equiv b \ \mathrm{mod},m $$

已知

则

升阶解 $f(x)\equiv0 \ \mathrm{mod} , p^{k+1}$ 具有形式 $$x\equiv a+t_{k}\cdot p^{k} \ \mathrm{mod},p^{k+1}$$
- $p \nmid f’(x_{k})$ $\implies$ 唯一解 $$t_{k} = \frac{-f(x_{k})}{p^{k}}\cdot(f’(x_{1})^{-1} \mathrm{mod} , p) \ \mathrm{mod} ,p$$
- $p \mid f’(x_{k})$
  - $p \nmid -\frac{f(x_{k})}{p^{k}}$ $\implies$ 无解
  - $p \mid -\frac{f(x_{k})}{p^{k}}$ $\implies$ $p$ 个解 $t_{k}=0,\dots,p-1$

注意

注意 $t_{k}$ 的定义式是等于，里面的取模都是算术运算而非同余运算 比如对于 $x^{3}+5x^{2}+9\equiv 0 \ \mathrm{mod},3^{2}$ 有 $x_{1} \equiv 1 \ \mathrm{mod},3$

那么 $$t_{1}=(-\frac{1^{3}+5\cdot1^{2}+9}{3}\cdot(3\cdot1^{2+10\cdot1 }% 3)) % 3$$

得到 $t_{1}=1$ 而不能直接用 $t_{k}\cdot p_{k}=-f(x_{k})\cdot(f^{-1}(x_{1}) % p)$

解

$$ f(x)\equiv 0 \ \mathrm{mod},p $$

【去高阶】用Fermat 小定理 $x^{p-1}\equiv 1 \ \mathrm{mod},p$ 简化 $f(x)$，使得 $\mathrm{deg},f<p$

注意

使用Fermat 小定理时先检查 $x\equiv 0 \ \mathrm{mod},p$ 是不是原方程的解！否则会漏解哦