Solving f(x) ≡ 0 (mod p^k) without Hensel's Lemma

Solving f(x) ≡ 0 (mod p^k) without Hensel's Lemma

Recall from the Hensel's Lemma page that if $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 $a + tp^k$ of $a$ such that $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 we can obtain a solution $a_{k+1}$ to $f(x) \equiv 0 \pmod {p^{k+1}}$ where $a_k$ is given recursively by:

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

Hensel's Lemma is very useful, however, if the condition that $f'(a) \not \equiv 0 \pmod p$ is satisfied then it cannot be applied. In that case, then one of the following is true:

  • 1. All of the lifts $a + tp^k$ of $a$ is a solution to $f(x) \equiv 0 \pmod {p^{k+1}}$.
  • 2. None of the lifts $a + tp^k$ of $a$ is a solution to $f(x) \equiv 0 \pmod {p^{k+1}}$.

Let's look at an example.

Example 1

Find all solutions to $x^{10} - 1 \equiv 0 \pmod {125}$.
\\Let $f(x) = x^{10} - 1$. Then we want to solve $f(x) \equiv 0 \pmod {5^3}$. We first find solutions to $f(x) \equiv 0 \pmod 5$. By trial and error we have that:

(2)
\begin{align} \quad f(0) &= 0^{10} - 1 = -1 \equiv 4 \pmod 5 \\ \quad f(1) &= 1^{10} - 1 = 0 \pmod 5 \\ \quad f(2) &= 2^{10} - 1 = 1024 - 1 = 1023 \equiv 3 \pmod 5 \\ \quad f(3) &= 3^{10} - 1 = 59049 - 1 = 59048 \equiv 3 \pmod 5 \\ \quad f(4) &= 4^{10} - 1 = 1048576 - 1 = 1048575 \equiv 0 \pmod 5 \end{align}

So $a = 1$ and $a = 4$ are solutions to $f(x) \equiv 0 \pmod 5$. We compute the derivative of $f(x)$. It is $f'(x) = 10x^9$. Observe that:

(3)
\begin{align} \quad f'(1) &= 10(1)^9 = 10 \equiv 0 \pmod 5 \\ \quad f'(4) &= 10(4)^9 = 10(262114) \equiv 10(4) \equiv 0 \pmod 5 \end{align}

We cannot apply Hensel's lemma to $a = 1$ or $a = 4$. Instead, we will use the note mentioned at the top of this page.

Set a = 1

First, for $a = 1$, the lifts are of the form $a + 5t$. They are $1, 6, 11, 16, 21$. Either all are solutions to $f(x) \equiv 0 \pmod {5^2}$ or none of them are. Testing $1$ gives us:

(4)
\begin{align} \quad f(1) = 1^{10} - 1 \equiv 0 \pmod {5^2} \end{align}

So $1, 6, 11,16, 21$ are all solutions to $f(x) \equiv 0 \pmod {5^2}$.

The lifts to the following possible solutions to $f(x) \equiv 0 \pmod {5^3}$ are listed in the table below:

$a$ Lifts $a + tp^2 = a + 25t$
$1$ $1, 26, 51, 76, 101$
$6$ $6, 31, 56, 81, 106$
$11$ $11, 36, 61, 86, 111$
$16$ $16, 41, 66, 91, 116$
$21$ $21, 46, 71, 96, 121$

For $1$ we test $1$ to get $f(1) = 1^{10} - 1 \equiv 0 \pmod {5^3}$ so $1, 26, 51, 76, 101$ are solutions to $f(x) \equiv 0 \pmod {125}$.

For $6$ we test $6$ to get $f(6) = 6^{10} - 1 \equiv 50 \pmod {5^3}$ so $6, 31, 56, 81, 106$ are NOT solutions to $f(x) \equiv 0 \pmod {125}$.

For $11$ we test $11$ to get $f(11) = 11^{10} -1 \equiv 100 \pmod {5^3}$ so $11, 36, 61, 86, 111$ are NOT solutions to $f(x) \equiv 0 \pmod {125}$.

For $16$ we test $16$ to get $f(16) = 16^{10} - 1 \equiv 25 \pmod {5^3}$ so $16, 41, 66, 91, 116$ are NOT solutions to $f(x) \equiv 0 \pmod {125}$.

For $21$ we test $21$ to get $f(21) = 21^{10} - 1 \equiv 75 \pmod {5^3}$ so $21, 46, 71, 96, 121$ are NOT solutions to $f(x) \equiv 0 \pmod {125}$.

Set a = 4

Second, for $a = 4$, the lifts are of the form $a + 5t$. They are $4, 9, 14, 19, 24$. Either all are solutions to $f(x) \equiv 0 \pmod {5^2}$ or none of them are. Testing $4$ gives us:

(5)
\begin{align} \quad f(4) = 4^{10} - 1 \equiv 0 \pmod {5^2} \end{align}

So $4, 9, 14, 19, 24$ are all solutions to $f(x) \equiv 0 \pmod {5^2}$.

The lifts of the following to possible solutions to $f(x) \equiv 0 \pmod {5^3}$ are listed in the table below:

$a$ Lifts $a + tp^2 = a + 25t$
$4$ $4, 29, 54, 79, 104$
$9$ $9, 34, 59, 84, 109$
$14$ $14, 39, 64, 89, 114$
$19$ $19, 44, 69, 94, 119$
$24$ $24, 49, 74, 99, 124$

For $4$ we test $4$ to get $f(4) = 4^{10} - 1 \equiv 75 \pmod {5^3}$ so $4, 29, 54, 79, 104$ are NOT solutions to $f(x) \equiv 0 \pmod {125}$.

For $9$ we test $9$ to get $f(9) = 9^{10} - 1 \equiv 25 \pmod {5^3}$ so $9, 34, 59, 84, 109$ are NOT solutions to $f(x) \equiv 0 \pmod {125}$.

For $14$ we test $14$ to get $f(14) = 14^{10} -1 \equiv 100 \pmod {5^3}$ so $14, 39, 64, 89, 114$ are NOT solutions to $f(x) \equiv 0 \pmod {125}$.

For $19$ we test $19$ to get $f(19) = 19^{10} - 1 \equiv 50 \pmod {5^3}$ so $19, 44, 69, 94, 119$ are NOT solutions to $f(x) \equiv 0 \pmod {125}$.

For $24$ we test $24$ to get $f(24) = 24^{10} - 1 \equiv 0 \pmod {5^3}$ so $24, 49, 74, 99, 124$ are solutions to $f(x) \equiv 0 \pmod {125}$.

All solutions

All solutions to $x^{10} - 1 \equiv 0 \pmod {125}$ are:

(6)
\begin{align} \quad x = 1, 26, 51, 76, 101, 24, 49, 74, 99, 124 \end{align}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License