Hensel's Lemma/First Form
Theorem
Let $p$ be a prime number.
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:
| \(\ds \map f {x_k}\) | \(\equiv\) | \(\ds 0\) | \(\ds \pmod {p^k}\) | |||||||||||
| \(\ds \map {f'} {x_k}\) | \(\not \equiv\) | \(\ds 0\) | \(\ds \pmod p\) |
 | This article, or a section of it, needs explaining. In particular: $f'$ You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Explain}} from the code. |
Then for every integer $l \ge 0$, there exists an integer $x_{k + l}$ such that:
| \(\ds \map f {x_{k + l} }\) | \(\equiv\) | \(\ds 0\) | \(\ds \pmod {p^{k + l} }\) | |||||||||||
| \(\ds x_{k + l}\) | \(\equiv\) | \(\ds x_k\) | \(\ds \pmod {p^k}\) |
and any two integers satisfying these congruences are congruent modulo $p^{k + l}$.
Moreover, for all $l \ge 0$ and any solutions $x_{k + l}$ and $x_{k + l + 1}$:
| \(\ds x_{k + l + 1}\) | \(\equiv\) | \(\ds x_{k + l} - \frac {\map f {x_{k + l} } } {\map {f'} {x_{k + l} } }\) | \(\ds \pmod {p^{k + l + 1} }\) | |||||||||||
| \(\ds x_{k + l + 1}\) | \(\equiv\) | \(\ds x_{k + l}\) | \(\ds \pmod {p^{k + l} }\) |
Proof
We use induction on $l$.
The base case $l = 0$ is trivial.
Let $l \ge 0$ be such that a solution $x_{k + l}$ exists and is unique up to a multiple of $p^{k + l}$.
Choose a solution $x_{k + l}$ satisfying:
| \(\ds \map f {x_{k + l} }\) | \(\equiv\) | \(\ds 0\) | \(\ds \pmod {p^{k + l} }\) | |||||||||||
| \(\ds x_{k + l}\) | \(\equiv\) | \(\ds x_k\) | \(\ds \pmod {p^k}\) |
By Congruence by Divisor of Modulus, 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 {p^{k + l} }$, hence is of the form $x_{k+ l} + t p^{k + l}$ with $t \in \Z$.
Let $d = \deg f$.
We have, for all $t \in \Z$:
| \(\ds \map f {x_{k + l} + t p^{k + l} }\) | \(=\) | \(\ds \map f {x_{k + l} } + t p^{k + l} \map {f'} {x_{k + l} } + \paren {t p^{k + l} }^2 m\) | for some $m \in \Z$, by Taylor Expansion for Polynomials: Order 1 | |||||||||||
| \(\ds \) | \(\equiv\) | \(\ds \map f {x_{k + l} } + t p^{k + l} \map {f'} {x_{k + l} }\) | \(\ds \pmod {p^{k + l + 1} }\) |
Because $\map {f'} {x_{k + l} } \equiv \map {f'} {x_k} \not \equiv 0 \pmod p$, $\map {f'} {x_{k + l} }$ is invertible modulo $p$.
 | This article needs to be linked to other articles. In particular: invertible modulo $p$ You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code. |
Thus $x_{k + l} + t p^{k + l}$ is a solution modulo $p^{k + l + 1}$ if and only if:
- $t \equiv - \dfrac {\map f {x_{k + l} } } {\map {f'} {x_{k + l} } } \pmod p$
Thus, necessarily:
- $x_{k + l + 1} \equiv x_{k + l} - \dfrac {\map f {x_{k + l} } } {\map {f'} {x_{k + l} } } \pmod {p^{k + l + 1} }$
which proves the existence and uniqueness.
By induction, we have shown uniqueness and existence for all $l \ge 0$, as well as the relations:
| \(\ds x_{k + l + 1}\) | \(\equiv\) | \(\ds x_{k + l} - \dfrac {\map f {x_{k + l} } } {\map {f'} {x_{k + l} } }\) | \(\ds \pmod {p^{k + l + 1} }\) | |||||||||||
| \(\ds x_{k + l + 1}\) | \(\equiv\) | \(\ds x_{k + l}\) | \(\ds \pmod {p^{k + l} }\) |
$\blacksquare$