Examples of Applying Hensel's Lemma

Examples of Applying Hensel's Lemma

Recall from the Hensel's Lemma page that if $f$ is a polynomial, $p$ is a prime, $x = a$ is a solution to $f(x) \equiv 0 \pmod {p^k}$, and $f'(a) \not \equiv 0 \pmod p$ then there exists a unique lift to a solution $a + tp^k$ where $f(a + tp^k) \equiv 0 \pmod {p^{k+1}}$. In particular, if $x = a_1$ is a solution to $f(x) \equiv 0 \pmod p$ and $f'(a_1) \not \equiv 0 \pmod p$ then the recursive formula:

(1)
\begin{align} 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}}$. We will now look at an example of applying Hensel's Lemma.

Example 1

Use Hensel's Lemma to find a solution to $x^3 - 2x \equiv 1 \pmod {125}$.

Let $f(x) = x^3 - 2x - 1$. We first find a solution to $f(x) \equiv 0 \pmod 5$. We see that:

(2)
\begin{align} \quad f(0) = -1 \equiv 4 \pmod 5 \\ \quad f(1) = -2 \equiv 3 \pmod 5 \\ \quad f(2) = 5 \equiv 0 \pmod 5 \\ \quad f(3) = 20 \equiv 0 \pmod 5 \\ \quad f(4) = 55 \equiv 0 \pmod 5 \end{align}

So $a_1 = 2, 3, 4$ are all solutions to $f(x) \equiv 0 \pmod 5$. We compute the derivative of $f$:

(3)
\begin{align} \quad f'(x) = 3x^2 - 2 \end{align}

Observe that:

(4)
\begin{align} \quad f'(2) = 12-2 = 10 \equiv 0 \pmod 5 \\ \quad f'(3) = 27-2 = 25 \equiv 0 \pmod 5 \\ \quad f'(4) = 48-2 = 46 \equiv 1 \pmod 5 \end{align}

We cannot apply Hensel's Lemma to $a_1 = 2, 3$, but we can apply Hensel's Lemma to $a_1 = 4$. Observe that $[f'(4)]^{-1} = 1 \pmod 5$. So:

(5)
\begin{align} \quad a_2 & \equiv 4 - f(4) [f'(4)]^{-1} \pmod {25} \\ & \equiv 4 - 55 \cdot 1 \pmod {25}\\ & \equiv -51 \pmod {25} \\ & \equiv 24 \pmod {25} \end{align}
(6)
\begin{align} \quad a_3 & \equiv 24 - f(24) [f'(4)]^{-1} \pmod {125} \\ & \equiv 24 - 13775 \cdot 1 \pmod {125} \\ & \equiv -13751 \pmod {125} \\ & \equiv -1 \pmod {125} \\ & \equiv 124 \pmod {125} \end{align}

So $x = 124$ is a solution to $x^3 - 2x \equiv 1 \pmod {125}$.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License