Hensel's Lemma
Let $p$ be an odd prime, $f \in \mathbb{Z}[x]$, and $m,r \in \mathbb{Z}$ such that $m>0$ and $f(r) \equiv 0 \mod p^m$. Then the following statements hold true.
- If $f^\prime (r) \not \equiv 0 \mod p$ and $f(r) \not \equiv 0 \mod p^{m+1}$, then there is a unique integer $t$ such that $1 \leq t \leq p-1$ and $f(r+tp^m) \equiv 0 \mod p^{m+1}$. Specifically, $t$ is determined by the equation $t \, f^\prime(r) \equiv -\frac{f(r)}{p^m} \mod p$.
- If $f^\prime(r) \equiv 0 \mod p$ and $f(r) \equiv 0 \mod p^{m+1}$, then for any $t$ such that $1 \leq t \leq p-1$, $f(r+tp^m) \equiv 0 \mod p^{m+1}$.
- If $f^\prime(r) \equiv 0 \mod p$ and $f(r) \not \equiv 0 \mod p^{m+1}$ then there is no integer $1 \leq t \leq p-1$ such that $f(r+tp^m) \equiv 0 \mod p^{m+1}$.
Example: "Lifting Solutions"
Let $f(x)=x^2+4x+23$.
Goal: Find the roots of $f(x)$ mod 625 using Hensel's Lemma.
Preliminary Thoughts: Note that $625=5^4$. This means that if we can find solutions to $f(r) \equiv 0 \mod 5$, we have a method of looking for solutions mod $5^4$ through Hensel's Lemma.
- p-step: By inspection, notice $f(2) = 4 + 8 + 23 = 35 \equiv 0 \mod 5$, so we can proceed solving the problem with Hensel's Lemma.
- $\bold{p^2}$-step: So now we check
- Is $f^\prime(2) \equiv 0 \mod 5$? (Note that $f^\prime(x) = 2x+4$)
- NO: $f^\prime(2) \equiv 3 \not \equiv 0 \mod 5$
- Is $f(2) \equiv 0 \mod 25$?
- NO: $f(2) \equiv 25 \equiv 10 \not \equiv 0 \mod 25$
- Is $f^\prime(2) \equiv 0 \mod 5$? (Note that $f^\prime(x) = 2x+4$)
Since neither $f^\prime(r) \equiv 0 \mod 5$ nor $f(r) \equiv 0 \mod 25$, Hensel's Lemma tells us that there is a unique integer $t$, with $1 \leq t \leq 4$, such that $f(r+5t) \equiv 0 \mod 25$, and $t$ is defined by $t \, f^\prime(2) \equiv - \frac{f(2)}{5} \mod 5$.
Using the values of $f^\prime(2)$ and $f(2)$ found above, we have
(1)It follows then that $f(2+1 \cdot 5) = f(7) \equiv 0 \mod 25$. Indeed, $f(7) = 100 \equiv 0 \mod 25$. We now have our solution mod 25.
- $\bold{p^3}$-step: We can now lift our solution mod $5^2$ to a solution mod $5^3$.
- Is $f(7) \equiv 0 \mod 5^3$?
- NO: $f(7) = 100 \not \equiv 0 \mod 125$.
- Is $f^\prime(7) \equiv 0 \mod 5$ ?
- NO: Notice that since $7 = 2 + 5$ we have $7 \equiv 2 \mod 5$. The upshot being that $f^\prime(7) \equiv f^\prime(2) \not \equiv 0 \mod 5$, and so you only have to check the derivative on the first step.
- Is $f(7) \equiv 0 \mod 5^3$?
Hensel's lemma now tells us that there is a unique $t$ such that $f(7+25t) \equiv 0 \mod 125$. Again with $1 \leq t \leq 4$ determined below.
(2)By Hensel's Lemma, $f(7 + 2 \cdot 25)=f(57) \equiv 0 \mod 125$. Indeed, $f(57) = 2500 \equiv 0 \mod 125$.
- $\bold{p^4}$-step: We can now lift our solution mod $5^3$ to a solution mod $5^4$. To do so we check?
- Is $f(57) \equiv 0 \mod 625$?
- NO: $f(57) = 3500 \not \equiv 0 \mod 625$
- Is $f(57) \equiv 0 \mod 625$?
Hensel's Lemma now tells us that there is a unique $t$ such that $f(7+125t) \equiv 0 \mod 625$, with $1 \leq t \leq 4$ determined below.
(3)So by Hensel's Lemma, $f(57+4*125) \equiv 0 \mod 125$. Indeed, $f(557) = 312,500 \equiv 0 \mod 625$.
Proof of Hensel's Lemma
Motivation: For a given polynomial $f(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_0$, with each coefficient $a_i$ an integer and $n \geq 0$, we know from calculus that we can find a value $h$ such that $f(x+h) \approx f(x) + h \, f^\prime(x)$. The idea here is that since we're only interested in integer values modulo $p^{m+1}$ things are somehow simpler, to the point where we can find an integer $h$ so that $f(x+h) \equiv f(x) + h \, f^\prime(x) \mod p^{m+1}$. This leads to a lemma.
Lemma: Let $p$ be a prime,$m>0$ an integer, and $f(x)=a_n x^n + \dots + a_0$ a polynomial with integer coefficients as before. Then for any integer $t$, we have
(4)Proof: To begin with, note that
(5)where if $j>1$, $p^{m+1} | (tp^m)^j$. Therefore we can say
(6)We can split the last sum up as
(7)which is immediately recognizable as $f(x) + tp^m \, f^\prime(x)$. Therefore, we have $f(x+tp^m) \equiv f(x)+tp^m \, f^\prime(x) \mod p^{m+1}$, as desired.
proof of Hensel's Lemma: From that lemma we can derive the three cases of Hensel's Lemma.
Case 1: Let $r$ be an integer such that $f(r) \equiv 0 \mod p^m$ and $f^\prime(r) \not \equiv 0 \mod p$. Note that this implies that $p^m | f(r)$, and $\frac{f(r)}{p^m} \not \equiv 0 \mod p$. Therefore we have a unique integer $t$, modulo $p$, such that $t \, f^\prime(r) \equiv -\frac{f(r)}{p^m} \mod p$. In other words, $t \, f^\prime(r) = -\frac{f(r)}{p^m} + kp$, for some integer $k$. The lemma then gives
(8)Therefore, there is exactly one $r^\prime \mod p^{m+1}$ such that $f(r^\prime) \equiv 0 \mod p^{m+1}$ and $r^\prime \equiv r \mod p^m$. Namely, $r^\prime \equiv r+tp^m \mod p^{m+1}$.
Case 2: Now suppose $f^\prime(r) \equiv 0 \mod p$ and that $f(r) \equiv 0 \mod p^{m+1}$. This implies that $f^\prime(r) = kp$, for some intger $k$. For any integer $t$, we then have
(9)Therefore, there are are $p$ many $r^\prime \mod p^{m+1}$ such that $f(r^\prime) \equiv 0 \mod p^{m+1}$ and $r^\prime \equiv r \mod p^m$.
Case 3: If, on the other hand, $f^\prime(r) \equiv 0 \modp$ but $f(r) \not \equiv 0 \mod p^{m+1}$, we still have $f^\prime(r)=kp$, however for any integer $t$
(10)Therefore, there are no $r^\prime \mod p^{m+1}$ such that $f(r^\prime) \equiv 0 \mod p^{m+1}$ and $r^\prime \equiv r \mod p^m$.
To finish things off, here is a nice method for solving quadratic congruence equation modulo an odd prime $p$. This provides a nice base step when applying Hensel's lemma to a quadratic equation.
Lemma(Quadratic Congruence Equations): Let $p$ be an odd prime and $f(x)=ax^2+bx+c$ such that $p \not | a$. The congruence equation $f(x) \equiv 0 \mod p$ has a solution if and only if $b^2-4ac$ is a quadratic residue modulo $p$.
Proof:
(11)