# Hensel's Lemma for Composite Numbers

## Theorem

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}}$

## Proof

We use induction on $l$.

The base case $l=0$ is trivial.

Let $l\geq0$ be such that a solution $x_{k+l}$ exists and is unique up to a multiple of $b^{k+l}$.

Choose a solution $x_{k+l}$.

Each solution $x_{k+l+1}$ is also a solution of the previous congruence.

By uniqueness, it has to satisfy $x_{k+l+1}\equiv x_{k+l}\pmod{b^{k+l}}$, hence is of the form $x_{k+l} + tb^{k+l}$ with $t\in\Z$.

Let $d=\deg f$.

We have:

\(\displaystyle f(x_{k+l} + tb^{k+l})\) | \(=\) | \(\displaystyle f(x_{k+l}) + tb^{k+l}f'(x_{k+l})+(tb^{k+l})^2 m\) | for some $m\in\Z$, by Taylor Expansion for Polynomials : Order 1 | ||||||||||

\(\displaystyle \) | \(\equiv\) | \(\displaystyle f(x_{k+l}) + tb^{k+l}f'(x_{k+l}) \pmod{b^{k+l+1} }\) |

Because $f'(x_{k+l})\equiv f'(x_k)\pmod b$, $f'(x_{k+l})$ is invertible modulo $b$.

Thus $x_{k+l} + tb^{k+l}$ is a solution modulo $b^{k+l+1}$ if and only if:

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

Thus, necessarily:

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

which proves the existence and uniqueness.

By induction, we have shown uniqueness and existence for all $l\geq0$, as well as the relations:

- $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}}$

$\blacksquare$