Hensel's lemma

Statement

Let $p$ be a prime number, and let $f$ be a polynomial with integer coefficients, with derivative $f'$. Let $r$ be an integer such that $f(r) \equiv 0 \pmod p$ and $f'(r) \not\equiv 0 \pmod p$. Then for each positive integer $k$ there is an integer $r_k$ with $r_k \equiv r \pmod p$ and $f(r_k) \equiv 0 \pmod{p^k}$. This $r_k$ is unique modulo $p^k$.

Remarks

The proof gives the lifts step by step. If $f(r_k) \equiv 0 \pmod{p^k}$ and $t$ is an inverse of $f'(r)$ modulo $p$, then $r_{k+1} = r_k - t f(r_k)$ is a root modulo $p^{k+1}$. For example, $3^2 \equiv 2 \pmod 7$ and $f'(3) = 6$ for $f = x^2 - 2$. The step gives $3 - 6 \cdot 7 = -39 \equiv 10 \pmod{49}$, and $10^2 = 100 \equiv 2 \pmod{49}$. In the language of $p$-adic numbers, a simple root modulo $p$ lifts to a unique root in the $p$-adic integers. The lemma is the analogue of Newton's method for congruences.

History

The lemma is named after Kurt Hensel.

Explanations

L1 human

A solution of a polynomial congruence modulo $p$ often gives solutions modulo $p^2$, $p^3$, and so on. The condition $f'(r) \not\equiv 0 \pmod p$ says that $r$ is a simple root modulo $p$. Under this condition, each step of the lifting has exactly one answer.