Hensel's Lemma
Recall from The Chinese Remainder Theorem page that the Chinese Remainder Theorem states that if $(m_i, m_j) = 1$ for all $i \neq j$ then the following system of linear congruences has a unique solution modulo $m_1m_2...m_k$.
(1)Let $p$ be a prime number. Suppose that we want to solve the linear congruence $x \equiv a \pmod {p^k}$. If $k = 1$ then solving this linear congruence is easy. If $k > 1$, then things become trickier. It is tempting to use the Chinese Remainder Theorem on the system:
(2)However the Chinese Remainder Theorem cannot be applied here since the moduli $(p, p^{k-1}) = p \neq 1$. More generally, if $f$ is a polynomial, then solving $f(x) \equiv 0 \pmod {p^k}$ can be difficult. However, if we know that $x \equiv a$ is a solution to $f(x) \equiv 0 \pmod {p^k}$ then it is possible to "lift" this solution to a solution for $f(x) \equiv 0 \pmod {p^{k+1}}$.
So suppose that $x \equiv a \pmod p^k$. Then we must have that for some $t$ with $0 \leq t < p$ that:
(3)If $f(a) \equiv 0 \pmod {p^k}$ then we want to determine if $f(a + tp^k) \equiv 0 \pmod {p^{k+1}}$. By Taylor expansion of $f$ is given by:
(4)Since $f$ is a polynomial this Taylor expansion must terminated, that is, there exists some integer $v$ such that $f^{(u)}(x) = 0$ for all $u > v$. But in particular, observe that, if $0 \equiv f(a + tp^k) \pmod {p^{k+1}}$ then:
(5)This is because $[tp^k]^z \equiv 0 \pmod {p^{k+1}}$ when $z \geq 2$. So:
(6)Now observe that since $p^k | f'(a) tp^k$ and $p^k | -f(a)$ (since $f(a) \equiv 0 \pmod {p^k}$ we have that:
(7)So we can actually solve for a unique $t$ provided that $(f'(a), p) = 1$, that is, when $f'(a) \not \equiv 0 \pmod p$. In this case we get that:
(8)Where $[f'(a)]^{-1}$ denotes the inverse of $f'(a)$ modulo $p$.
Lemma (Hensel's Lemma): Let $f$ be a polynomial and suppose that $x = a_1$ is a solution to $f(x) \equiv 0 \pmod {p^k}$ and that $f'(a_1) \not \equiv 0 \pmod p$. Then there exists a unique lift of the solution $a$ to $a_1 + tp^k$ where $f(a_1 + tp^k) \equiv 0 \pmod {p^{k+1}}$. More generally, if $x = a_1$ is a solution to $f(x) \equiv 0 \pmod p$ and $f'(a_1) \not \equiv 0 \pmod p$ then we can obtain a solution to $a_{k+1}$ to $f(x) \equiv 0 \pmod {p^{k+1}}$ by the recursive formula $a_{k+1} \equiv a_k - f(a_k)[f'(a_1)] \pmod {p^{k+1}}$. |
- Proof: If $x = a_1$ is a solution to $f(x) \equiv 0 \pmod p$ and $f'(a_1) \not \equiv 0 \pmod p$ then from above there exists a unique $t$ such that:
- And such that $f(a + tp) \equiv 0 \pmod {p^2}$. We see that:
- In general, it is easy to verify that the recursive formula:
- is a solution to $f(x) \equiv 0 \pmod {p^{k+1}}$. $\blacksquare$
If $x = a$ is a solution to $f(x) \equiv 0 \pmod {p^k}$ but the condition $f'(a) \not \equiv 0 \pmod p$ is satisfied, then the following corollary tells us exactly what to do.
Corollary 2: Let $x = a$ be a solution to $f(x) \equiv 0 \pmod {p^k}$. If $f'(a) \equiv 0 \pmod p$ then either all or none of $a + tp^k$ for $0 \leq t < p$ are solutions to $f(x) \equiv 0 \pmod {p^{k+1}}$. |