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)

\begin{align} \quad \left\{\begin{matrix} x \equiv a_1 \pmod m_1\\ x \equiv a_2 \pmod m_2\\ \vdots \\ x \equiv a_k \pmod m_k \end{matrix}\right. \end{align}

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)

\begin{align} \quad \left\{\begin{matrix} x \equiv a \pmod p\\ x \equiv a \pmod p^{k-1}\\ \end{matrix}\right. \end{align}

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)

\begin{align} \quad x \equiv a + tp^k \pmod {p^{k+1}} \end{align}

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)

\begin{align} \quad f(a + tp^k) = f(a) + f'(a) tp^k + \frac{f''(a)}{2!} [tp^k]^2 + \frac{f'''(a)}{3!} [tp^k]^3 + ... \end{align}

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)

\begin{align} 0 &\equiv f(a + tp^k) \pmod {p^{k+1}} \\ & \equiv f(a) + f'(a) tp^k + \frac{f''(a)}{2!} [tp^k]^2 + \frac{f'''(a)}{3!} [tp^k]^3 + ... \pmod {p^{k+1}} \\ & \equiv f(a) + f'(a) tp^k + 0 \pmod {p^{k+1}} \end{align}

This is because $[tp^k]^z \equiv 0 \pmod {p^{k+1}}$ when $z \geq 2$. So:

(6)

\begin{align} \quad f'(a) tp^k \equiv -f(a) \pmod {p^{k+1}} \end{align}

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)

\begin{align} \quad f'(a) t \equiv - \frac{f(a)}{p^k} \pmod p \end{align}

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)

\begin{align} \quad t \equiv - [f'(a)]^{-1}\frac{f(a)}{p^k} \pmod p \end{align}

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:

(9)

\begin{align} \quad t \equiv - [f'(a_1)]^{-1} \frac{f(a_1)}{p} \pmod p^2 \end{align}

• And such that $f(a + tp) \equiv 0 \pmod {p^2}$. We see that:

(10)

\begin{align} \quad a_1 + tp &= a_1 + \left [ - [f'(a_1)]^{-1} \frac{f(a_1)}{p} \right ]p \pmod {p^2} \\ &= a_1 - f(a_1)[f'(a_1)]^{-1} \pmod {p^2} \end{align}

• In general, it is easy to verify that the recursive formula:

(11)

\begin{align} \quad a_{k+1} \equiv a_k - f(a_k)[f'(a_1)]^{-1} \pmod {p^{k+1}} \end{align}

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