高次同余式

高次同余式解数

若$m=m_1\cdots m_k$，则同余式$f\left(x\right)\equiv0\left(\mod m\right)$与同余式组

等价。若$T_i$为同余式$f\left(x\right)\equiv 0\left(\mod m_i\right)$的解数，则同余式解数$T=T_1\cdots T_k$

高次同余式求解

$f\left(x\right)\equiv0\left(\mod p^\alpha\right)$

• STEP1: 验证有解

  $x=x_1\left(\mod p\right)$为$f\left(x\right)\equiv0\left(\mod p\right)$的一个解，$\left(f^\prime\left(x_1\right),p\right)=1$

• STEP2: 递推

  $x\equiv x_\alpha\left(\mod p^\alpha\right)$