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