Hensel's Lemma

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.

1. 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$.
2. 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}$.
3. 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$

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)

\begin{align} tf^\prime(2) \equiv -\frac{f(2)}{5} & \mod 5 \\ 3t \equiv -\frac{35}{5} &\mod 5 \\ 3t \equiv -7 & \mod 5 \\ 3t \equiv 3 & \mod 5 \\ t \equiv 1 & \mod 5 \end{align}

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.

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)

\begin{align} tf^\prime(7) \equiv -\frac{f(7)}{25} & \mod 5 \\ 3t \equiv -4 & \mod 5 \\ 3t \equiv 1 & \mod 5 \\ t \equiv 2 & \mod 5 \end{align}

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$

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)

\begin{align} tf^\prime(57) \equiv -\frac{f(57)}{125} & \mod 5 \\ 3t \equiv -\frac{3500}{125} & \mod 5 \\ 3t \equiv -28 & \mod 5 \\ 3t \equiv 2 & \mod 5 \\ t \equiv 4 & \mod 5 \end{align}

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)

\begin{align} f(x+tp^m) \equiv f(x) + tp^m \, f^\prime(x) \end{align}

Proof: To begin with, note that

(5)

\begin{align} f(x+tp^m) = a_0 \sum_{i=1}^n a_i(x+tp^m)^i = a_0 + \sum_{i=1}^n \left ( a_i \sum_{j=0}^i \binom{i}{j}x^{i-j}(tp^m)^j \right ) \end{align}

where if $j>1$, $p^{m+1} | (tp^m)^j$. Therefore we can say

(6)

\begin{align} a_0 + \sum_{i=1}^n \left ( a_i \sum_{j=0}^i \binom{i}{j}x^{i-j}(tp^m)^j \right ) \equiv a_0 + \sum_{i=1}^n \left ( a_i \sum_{j=0}^1 \binom{i}{j}x^{i-j}(tp^m)^j \right ) \mod p^{m+1} \end{align}

We can split the last sum up as

(7)

\begin{align} a_0 + \sum_{i=1}^n a_i x^i + \sum_{i=1}^nix^{i-1}tp^m = a_0 + a_1 + \dots + a_n x^n + tp^m(a_1 + 2a_2x + \dots + na_nx^{n-1}) \end{align}

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)

\begin{align} f(r+tp^m) \equiv f(r) + tp^m \, f^\prime(r) = f(r) + p^m \left (-\frac{f(r)}{p^m} + kp \right ) = f(r) - f(r) + kp^{m+1} \equiv 0 \mod p^{m+1} \end{align}

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)

\begin{align} f(r+tp^m) \equiv f(r) + tp^m \, f^\prime(x) = f(r) + tkp^{m+1} \equiv 0 \mod p^{m+1} \end{align}

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)

\begin{align} f(r+tp^m) \equiv f(r) + tp^m \, f^\prime(r) = f(r) + tkp^{m+1} \equiv f(r) \not \equiv 0 \mod p^{m+1} \end{align}

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)

\begin{align} f(x) = ax^2+bx+c \equiv 0 \mod p & \iff \\ 4a^2x^2+4abx+4ac \equiv 0 \mod p & \iff \\ 4a^2x^2 + 4abc+4ac+b^2+4ac \equiv b^2 +4ac \mod p & \iff \\ (2ax+b)^2 \equiv b^2 - 4ac \mod p & \end{align}