高次同余式

高次同余式解数

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

\left\{ \begin{array}{**lr**} f\left(x\right)\equiv 0\left(\mod m_1\right) &\\ \vdots &\\ f\left(x\right)\equiv 0\left(\mod m_k\right) \end{array} \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)$

  \left\{ \begin{array}{**lr**} t_{i-1}\equiv-\frac{f\left(x_{i-1}\right)}{p^{i-1}}\cdot\left({f^\prime\left(x_1\right)}^{-1}\left(\mod p\right)\right)\left(\mod p\right) &\\ x_i\equiv x_{i-1}+t_{i-1}\cdot p^{i-1}\left(\mod p^i\right) &\\ i=2,\cdots,a \end{array} \right.