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 \set {-1, 0, 1}$ be an integer.
Let $k > 0$ be a positive integer.
Let $\map f X \in \Z \sqbrk X$ be a polynomial.
Let $x_k \in \Z$ such that:
- $\map f {x_k} \equiv 0 \pmod {b^k}$
- $\gcd \set {\map {f'} {x_k}, b} = 1$
Then for every integer $l \ge 0$, there exists an integer $x_{k + l}$ such that:
- $\map 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 \ge 0$ and any solutions $x_{k + l}$ and $x_{k + l + 1}$:
- $x_{k + l + 1} \equiv x_{k + l} - \dfrac {\map f {x_{k + l} } } {\map {f'} {x_{k + l} } } \pmod {b^{k + l + 1} }$
- $x_{k + l + 1} \equiv x_{k + l} \pmod {b^{k + l} }$
$p$-adic Integers
Let $\Z_p$ be the $p$-adic integers for some prime $p$.
Let $\map F X \in \Z_p \sqbrk X$ be a polynomial.
Let $\map {F'} X$ be the (formal) derivative of $F$.
Let $p\Z_p$ denote the principal ideal of $\Z_p$ generated by $p$.
For all $x,y \in \Z_p$, let:
- $x \equiv y \pmod {p\Z_p}$
denote congruence modulo the principal ideal $p\Z_p$.
Let $\alpha_0 \in \Z_p$ be a $p$-adic integer:
- $\map F {\alpha_0} \equiv 0 \pmod {p\Z_p}$
- $\map {F'} {\alpha_0} \not\equiv 0 \pmod {p\Z_p}$
Then there exists a unique $\alpha \in \Z_p$:
- $\alpha \equiv \alpha_0 \pmod {p\Z_p}$
- $\map F {\alpha} = 0$
Source of Name
This entry was named for Kurt Wilhelm Sebastian Hensel.