Hensel's Lemma

Suppose that we know that a polynomial $f(x)$ has a root modulo $p^k$. Can we tell if it has a root modulo $p^{k+1}$? Hensel's lemma states that it is possible under certain conditions.

Hensel's lemma Let $f(x)\in\mathbb{Z}[x]$, and $a,p\in\mathbb{Z}$, where $p$ is prime. If $f(a)\equiv 0\pmod{p}$ and $f'(a)\not\equiv 0\pmod{p}$, then there exists $a_n\in\mathbb{Z}/{p^n}\mathbb{Z}$ such that $f(a_n)\equiv 0\pmod{p^n}$ and $a_n\equiv a_{n-1}\pmod{p^{n}}$ for all $n\in\mathbb{N}$.

Let's try to prove it now:

Let $r$ be a root of $f$. By induction, it suffices to show that if $f(r)\equiv 0\pmod{p}$, then $f(r+tp^{n})\equiv 0\pmod{p^{n+1}}$ for some $t\in\mathbb{Z}$.

Let $f(x)=\sum\limits^n_{i=0}a_ix^i$. Now suppose that $f(r)\equiv 0\pmod{p^k}$. Then $$f(r+tp^k)=\sum\limits^n_{i=0}a_i(r+tp^k)^i.$$ Note that $f(r+tp^{n})\equiv 0\pmod{p^{n+1}}$ for some $t$ if and only if $$0\equiv \sum\limits^n_{i=0}a_i(r+tp^n)^i\pmod {p^{n+1}}.$$

Note that by the binomial theorem, $(r+tp^n)^i\equiv r^i+r^{i-1}\dbinom{i}{1}tp^k\pmod{p^{n+1}}$. Thus, $$\begin{align*} 0&\equiv \sum\limits^n_{i=0}a_i\left(r^i+r^{i-1}\dbinom{i}{1}tp^n\right)\pmod{p^{n+1}}\\ &\equiv \sum\limits^n_{i=0}a_i r^i+\sum\limits^n_{i=0}a_ir^{i-1}\dbinom{i}{1}tp^n\pmod{p^{n+1}}\\ &\equiv f(r)+f'(r)tp^n\pmod{p^{n+1}}. \end{align*}$$ Since $f(r)\equiv 0\pmod{p^n}$, we have $f(r)=p^nk$ for some $k\in\mathbb{Z}$. Thus, $$0\equiv (k+f'(r)t)p^n\pmod{p^{n+1}},$$ and thus $$0\equiv k+f'(r)t\pmod{p}.$$ Solving gives $t\equiv -k(f'(r))^{-1}\pmod{p}$, which is valid because $f'(r)\neq 0$. Hence, we have found a $t$, and there exists $a_n\in\mathbb{Z}/{p^n}\mathbb{Z}$ such that $f(a_n)\pmod{p^n}$ and $a_n\equiv a_{n-1}\pmod{p^{n}}$ for all $n\in\mathbb{N}$.

Since Diophantus, mathematicians have been interested in the integer solutions to polynomial equations $f(x) = 0$. But number theorists are interested in other questions, like how many solutions a polynomial might have modulo $p$ or $p^2$ or $p^3$, etc., where $p$ is a prime number. Hensel's Lemma gives us one way to try to count the solutions modulo $p^2$ if we know something about the solutions modulo $p$.

Particularly, if $f$ is a polynomial with integer coefficients and $f(r) \equiv 0 \pmod{p}$, and the derivative $f'(r) \not \equiv 0 \pmod{p}$, then there exists a unique $s \equiv r \pmod{p}$, such that $f(s) \equiv 0 \pmod{p^2}$. In fact, we can determine $s$ via $$s := r - f'(r)^{-1} f(r).$$ You may notice this looks a bit like Newton's method and that's because Hensel's Lemma is derived from the Taylor expansion of $f$ around $r$.

Moreover, if $f'(r)=0$, then for any $s \equiv r \pmod{p}$ we have $$f(s) \equiv f(r)\pmod{p^2}.$$ So either all or none of $s\equiv r\pmod{p}$ are solutions for $f(s) \equiv 0 \pmod{p^2}$.