# Hensel's Lemma

Based on previous results (Chinese Remainder Theorem and the Multiplicative Property of Solutions), solving the polynomial congruence $f(x) \equiv 0 \pmod{m}$ is reduced to solving $f(x) \equiv 0 \pmod{p^k}$ for each prime power $p^k$ dividing $m$.

Hensel's Lemma is used to **"lift" a solution** $r$ from a smaller prime power modulus $p^{k-1}$ to a larger one $p^k$.

:::danger
**Theorem (Hensel’s Lemma)**
Let $f(x)$ be a polynomial with integer coefficients, let $p$ be a prime, and let $k \ge 2$. Suppose $r$ is a solution to $f(r) \equiv 0 \pmod{p^{k-1}}$.

1. *(Non-Singular Case)* If $f'(r) \not\equiv 0 \pmod{p}$: There exists a unique integer $t$ with $0 \le t < p$ such that $x=r+tp^{k−1}$ is a solution to $f(x) \equiv 0 \pmod{p^k}$. The value of $t$ is given by: $$t \equiv -\frac{f(r)}{p^{k-1}} \cdot \overline{f'(r)} \pmod{p}$$
2. *(Singular Case)* If $f'(r) \equiv 0 \pmod{p}$:
* If $f(r) \equiv 0 \pmod{p^k}$, then $x = r + t p^{k-1}$ is a solution for all $t=0, 1, \dots, p-1$. This yields $p$ solutions modulo $p^k$.
* If $f(r) \not\equiv 0 \pmod{p^k}$, then there is no solution modulo $p^k$ that is congruent to $r$ modulo $p^{k-1}$.
:::

## Examples of Hensel's Lemma
:::warning
**Example (Non-Singular Case)** Solve $x^3 + x^2 + 29 \equiv 0 \pmod{25}$

* **Mod 5:** $f(x) = x^3 + x^2 + 29 \equiv x^3 + x^2 - 1 \equiv 0 \pmod{5}$. The unique solution is $r=3$.
* **Derivative Check:** $f'(x) = 3x^2 + 2x$. $f'(3) = 33 \equiv 3 \pmod{5}$. Since $3 \not\equiv 0 \pmod{5}$, the solution is unique (Case 1).
* **Lift to Mod 25:** We compute $t$: $f(3) = 65$, so $\frac{f(3)}{5} = 13 \equiv 3 \pmod{5}$. The inverse of $f'(3) \equiv 3 \pmod{5}$ is $\overline{3} \equiv 2 \pmod{5}$. $$t \equiv -3 \cdot 2 = -6 \equiv 4 \pmod{5}$$
* **Solution:** $x = r + tp = 3 + 4(5) = 23$. The unique solution is $x \equiv 23 \pmod{25}$.
:::

:::warning
**Examples (Singular Case with Splitting)** Solve $x^2 + x + 7 \equiv 0 \pmod{27}$.

* **Mod 3:** $f(x) = x^2+x+7 \equiv x^2+x+1 \equiv 0 \pmod{3}$. Unique solution: $r=1$.
* **Derivative Check:** $f'(1) = 2(1)+1 = 3 \equiv 0 \pmod{3}$. (Case 2 applies).
* **Lift to Mod 9 ($p^2$):** $f(1)=9$. Since $f(1) \equiv 0 \pmod{9}$, there are $p=3$ solutions of the form $x=1+3t \pmod{9}$, for $t=0,1,2$. The solutions are $x \equiv 1, 4, 7 \pmod{9}$.
* **Lift to Mod 27 ($p^3$):**
* $x \equiv 1 \pmod{9}$: $f(1)=9$. Since $9 \not\equiv 0 \pmod{27}$, *no solution* for this branch.
* $x \equiv 4 \pmod{9}$: $f(4)=27$. Since $27 \equiv 0 \pmod{27}$, there are $p=3$ solutions: $x \equiv 4, 13, 22 \pmod{27}$.
* $x \equiv 7 \pmod{9}$: $f(7)=63$. Since $63 \not\equiv 0 \pmod{27}$, no solution for this branch.
* **Final Solutions:** $x \equiv 4, 13, 22 \pmod{27}$.
:::

:::warning
**Example (Singular Case with Failure to Lift)**
Let $f(x) = x^2 + 2x + 50$ and $p = 7$.

* **Mod 7:** $f(x) \equiv x^2 + 2x + 1 \equiv (x+1)^2 \equiv 0 \pmod{7}$. Unique solution: $r=6$.
* **Derivative Check:** $f'(x) = 2x+2$. $f'(6) = 14 \equiv 0 \pmod{7}$. (Singular Case 2).
* **Lift to Mod 49 ($p^2$):** $f(6) = 98$. Since $98 \equiv 0 \pmod{49}$, there are $p=7$ solutions of the form $x = 6 + 7\ell \pmod{49}$. This case is always satisfied.
* **Lift to Mod 343 ($p^3$):** The condition simplifies to $(\ell+1)^2 \equiv -1 \pmod{7}$.
* Since $-1$ is **not a quadratic residue** modulo 7, this congruence has no solutions. Hence, there are no solutions to $x^2 + 2x + 50 \equiv 0 \pmod{7^n}$ for $n \ge 3$.
:::

:::success
**Exercise**
How many incongruent solutions are there to the congruence $x^5 + x - 6 \equiv 0 \pmod{144}$?
:::