# Hensel's Lemma

## Lemma

### First Form

Let $p$ be a prime number.

Let $k > 0$ be a positive integer.

Let $f \left({X}\right) \in \Z \left[{X}\right]$ be a polynomial.

Let $x_k \in \Z$ such that:

$f \left({x_k}\right) \equiv 0 \pmod {p^k}$
$f' \left({x_k}\right) \not \equiv 0 \pmod p$

Then for every integer $l \ge 0$, there exists an integer $x_{k + l}$ such that:

$f \left({x_{k + l} }\right) \equiv 0 \pmod {p^{k + l} }$
$x_{k + l}\equiv x_k \pmod {p^k}$

and any two integers satisfying these congruences are congruent modulo $p^{k + l}$.

Moreover, for all $l\geq0$ and any solutions $x_{k + l}$ and $x_{k + l + 1}$:

$x_{k + l + 1} \equiv x_{k + l} - \dfrac {f \left({x_{k + l} }\right)} {f' \left({x_{k + l} }\right)} \pmod {p^{k + l + 1} }$
$x_{k + l + 1} \equiv x_{k + l} \pmod {p^{k + l} }$

### Composite Numbers

Let $b\in\Z\setminus\{-1,0,1\}$ be an integer.

Let $k>0$ be a positive integer.

Let $f(X) \in \Z[X]$ be a polynomial.

Let $x_k\in\Z$ such that:

$f(x_k)\equiv 0 \pmod{b^k}$
$\gcd(f'(x_k),b)=1$

Then for every integer $l\geq 0$, there exists an integer $x_{k+l}$ such that:

$f(x_{k+l})\equiv 0 \pmod{b^{k+l}}$
$x_{k+l}\equiv x_k\pmod{b^k}$

and any two integers satisfying these congruences are congruent modulo $b^{k+l}$.

Moreover, for all $l\geq0$ and any solutions $x_{k+l}$ and $x_{k+l+1}$:

$x_{k+l+1}\equiv x_{k+l}-\frac{f(x_{k+l})}{f'(x_{k+l})}\pmod{b^{k+l+1}}$
$x_{k+l+1}\equiv x_{k+l}\pmod{b^{k+l}}$

## Source of Name

This entry was named for Kurt Wilhelm Sebastian Hensel.