首先我们来看看为书上是怎么写的

# 定理 2.18

如果我们要解方程 $f(x)\equiv 0\pmod {p^{k+1}}$，由之前的知识可知，这个方程的解一定可以从 $f(x)\equiv 0\pmod{p^k}$ 中筛选出来

即假设 $x\equiv x_k\pmod {p^{k}}$ 是方程 $f(x)\equiv 0\pmod{p^k}$ 的一个特解，那么 $x=x_k+p^kt,t\in Z$ 都是这个方程的解

那么 $f(x)\equiv 0\pmod {p^{k+1}}$ 的解一定是通过约束 $t$ 之后的 $x=x_k+p^kt$

我们可以把解 $x=x_k+p^kt$ 带入 $f(x)\equiv 0\pmod {p^{k+1}}$ 中，找到 $t$ 的范围，让这个等式成立即可

$$\Rightarrow f(x_k+p^kt)\equiv 0\pmod {p^{k+1}}$$

由泰勒公式展开得

$$f(x_k)+f'(x_k)p^kt+\sum_{i=2}^n\frac{f^i(x_k)p^{ik}t^i}{i!}\equiv 0\pmod {p^{k+1}}$$

显然 $i!|f^i(x_k)$，对于 $i\geq 2,p^{k+1}|p^{ik}$，所以 $\sum_{i=2}^n\frac{f^i(x_k)p^{ik}t^i}{i!}$ 这一项就可以被消掉了

式子就变成

$$f(x_k)+f'(x_k)p^kt\equiv 0\pmod {p^{k+1}}$$

我们来尝试化简这个式子

首先将这个同余式转换成等式①

$$f(x_k)+f'(x_k)p^kt=m\cdot p^{k+1} -- ①$$

其中，$m$ 是整数

又因为 $f(x_k)\equiv 0\pmod{p^k}$，我们可以得到等式②

$$f(x_k)=n\cdot p^k --②$$

其中， $n$ 是整数

那么由 等式 ① 和等式 ② 我们可以得到

$$n\cdot p^k+f'(x_k)p^kt=m\cdot p^{k+1}\\ \Rightarrow n+f'(x_k)t=m\cdot p\\ \Rightarrow f'(x_k)t=-n+m\cdot p$$

将 $n=\frac{f(x_k)}{p^k}$ 带入，得到

$$f'(x_k)t\equiv -\frac{f(x_k)}{p^k}\pmod p$$

我们要求解方程

$$f(x)\equiv 0\pmod {p^{k+1}}$$

它的解是

$$x=x_k+p^kt$$

$t$ 的约束条件是

$$f'(x_k)t\equiv -\frac{f(x_k)}{p^k}\pmod p$$

$x\equiv x_k\pmod {p^{k}}$ 是方程 $f(x)\equiv 0\pmod{p^k}$ 的一个解，那么在这个剩余类中：

1. 如果 $(f'(x_k),p)=1$，那么同余式 $f(x)\equiv 0\pmod{p^{k+1}}$ 有唯一解

   $$x=x_k-f(x_k)((f'(x_k))^{-1}\pmod p)\pmod{p^{k+1}}$$

2. 如果 $p|f'(x_k)$

   • $f(x_k)\not\equiv 0\pmod {p^{k+1}}$ 时，无解
   • $f(x_k)\equiv 0\pmod {p^{k+1}}$ 时，有 $p$ 个解，即 $x = x_k+p^kt\pmod{p^{k+1}},t=0,1,...,p-1$

# 推论

由刚刚的证明可知 ，上述的 $x$ 即表示 x_

所以 ，在 $(f'(x_k),p)=1$ 的情况下，$x\equiv x_k\pmod {p^k}$ 剩余类的解为

$$x_{k+1}=x_k-f(x_k)((f'(x_k))^{-1}\pmod p)\pmod{p^{k+1}}$$