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)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:
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)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)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)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)