设 `f(x)` 为整系数多项式, `p` 是素数, `m` 是正整数, 如何求同余方程 `f(x) -= 0 (mod p^m)` 的解? Hensel 引理给出一个解答:
Hensel 引理 [来自 yangdong02] 假设 `m ge 2`. 先求 `f(x) -= 0` `(mod p^(m-1))` 的解, 设 `x -= c` `(mod p^(m-1))` 是这样的一个解. 那么原方程 `f(x) -= 0` `(mod p^m)` 的解中满足 `x -= c` `(mod p^(m-1))` 的解形如 `x -= y p^(m-1) + c` `quad (mod p^m)`, 这里的 `y` 满足 `f'(c) y + f(c) p^(1-m) -= 0` `quad (mod p)`.
设 `f(x) = sum_(k=0)^n a_k x^k`, 将 `x -= y p^(m-1) + c (mod p^m)` 代入得,
`f(x) -= sum_(k=0)^n a_k (y p^(m-1) + c)^k`
`-= sum_(k=0)^n a_k (c^k + k c^(k-1) y p^(m-1) + cdots)`
`quad (mod p^m)`,
二项式展开被省略的那些项, `p` 的次数至少是 `p^m`, 因此它们模 `p^m` 余 0, 得到
`0 -= f(x) -= f(c) + f'(c) y p^(m-1)` `quad (mod p^m)`.
由于 `f(c) -= 0 (mod p^(m-1))`, 上式同除以 `p^(m-1)` 即得结论.
类比于牛顿迭代的 `0 = f(x) ~~ f(c) + f'(c)(x-c)`,
Hensel 引理也可以写为
`x - c -= y p^(m-1)` `quad (mod p^m)`,
`f(c) + f'(c) (x-c) -= 0` `quad (mod p^m)`.