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 to solving $f(x) \equiv 0 \pmod {p^k}$.

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

Example 2

Use Hensel's Lemma to find all solutions to $x^4 + x^3 + 2x^2 + x \equiv 13 \pmod {343}$.

Let $f(x) = x^4 + x^3 + 2x^2 + x - 13$. Then $f(x) \equiv 0 \pmod {7^3}$. We attempt to find a solution to $f(x) \equiv 0 \pmod 7$. We have that:

(7)
\begin{align} \quad f(0) &= -13 \equiv 1 \pmod 7 \\ \quad f(1) &= -8 \equiv 6 \pmod 7 \\ \quad f(2) &= 21 \equiv 0 \pmod 7 \\ \quad f(3) &= 116 \equiv 4 \pmod 7 \\ \quad f(4) &= 343 \equiv 0 \pmod 7 \\ \quad f(5) &= 792 \equiv 1 \pmod 7\\ \quad f(6) &= 1577 \equiv 2 \pmod 7 \end{align}

Let $s = 2$ and $t = 4$. Then $s$ and $t$ are solutions to $f(x) \equiv 0 \pmod p$. Now the derivative of $f(x)$ is:

(8)
\begin{equation} f'(x) = 4x^3 + 3x^2 + 4x + 1 \end{equation}

Plugging in $s$ and $t$ into $f'$ gives us:

(9)
\begin{align} \quad f'(s) = f'(2) = 53 \equiv 4 \not \equiv 0 \pmod 7 \\ \quad f'(t) = f'(4) = 321 \equiv 6 \not \equiv 0 \pmod 7 \end{align}

So Hensel's Lemma can be applied to both $s$ and $t$.

First set $a_1 = 2$. From above we have that $f'(2) = 4$. So $[f'(2)]^{-1} = [4]^{-1} = 2 \pmod 7$. Hence:

(10)
\begin{align} \quad a_2 & \equiv a_1 - f(a_1)[f'(2)]^{-1} \pmod {7^2} \\ & \equiv 2 - f(2) \cdot 2 \pmod {7^2} \\ & \equiv 2 - 21 \cdot 2 \pmod {7^2} \\ & \equiv 2 - 42 \pmod {7^2} \\ & \equiv -40 \pmod {7^2} \\ & \equiv 9 \pmod {7^2} \end{align}

And:

(11)
\begin{align} \quad a_3 & \equiv a_2 - f(a_2)[2] \pmod {7^3} \\ & \equiv 9 - f(9)[2] \pmod {7^3} \\ & \equiv 9 - [7448][2] \pmod {7^3} \\ & \equiv 205 \pmod {7^3} \end{align}

So $x = 205$ is a solution to $f(x) \equiv 0 \pmod {7^3}$.

Setting $a_1 = 4$ and using the same process shows that $x = 4$ is also a solution to $f(x) \equiv 0 \pmod {7^3}$.

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