Hensel's Lemma

Hensel's Lemma is a important result in Number Theory for solving polynomial congruences. It is named after the German mathematician Kurt Hensel, who derived it.

Statement

Suppose that $f(x)$ is a polynomial function with integer coefficients and let $p$ be a prime number. Also, let $k$ be an arbitrary integer with $k \ge 2$ . Suppose further that $r$ is a solution to the congruence $f(x) \equiv 0 \pmod {p^{k-1}}$ . From here, there are three cases to consider:

If $f'(r)$ is not congruent to $0$ modulo $p$ , then there exists a unique integer $t \in [0,p)$ such that $f(r+t \cdot p^{k-1}) \equiv 0 \pmod {p^k}$ , given by

$t=-u \cdot \frac{f(r)}{p^{k-1}},$

where $u$ denotes the inverse of $f(r)$ modulo $p$ .

If $f'(r) \equiv f(r) \equiv 0 \pmod {p}$ , then $f(r+t \cdot p^{k-1}) \equiv 0 \pmod {p^k}$ for all integers $t$ .

If $f'(r) \equiv 0 \pmod {p}$ but $f(r)$ is not congruent to $0$ modulo $p$ , then $f(x) \equiv 0 \pmod {p^{k-1}}$ have no solutions with $x \equiv r \pmod {p^{k-1}}$ .

Each time we bring up the exponent of $p$ , it is said that we have performed a lift.

Proof

As in the hypothesis, $r$ is an integer such that $f(r) \equiv 0 \pmod {p^{k-1}}$ . If $r'$ satisfy $f(r') \equiv 0 \pmod {p^{k}}$ , then we must have $r \equiv r' \pmod {p^{k-1}}$ so $r'=r+t \cdot p^{k-1}$ for some integer $t$ .

By the formula for Taylor Series (of point $x=a+b$ around the point $x=a$ ),

$f(a+b)=f(a) +f'(a) \cdot b + f''(a) \cdot \frac{b^2}{2!} + \cdot + f^{(n)} (a) \cdot {b^n}{n!}$

We plug in $a=r$ and $b=t \cdot p^{k-1}$ :

$f(r')=f(r+t \cdot p^{k-1})=f(r)+f'(r) \cdot t \cdot p^{k-1} + f''(r) \cdot \frac{t^2 \cdot p^{2k-2}}{2!} + \dots + f^{(n)} (r) \cdot \frac{t^n \cdot p^{nk-n}}{n!} \equiv f(r)+f'(r) \cdot t \cdot p^{k-1} \pmod {p^k}$

The result for each case follow from the above equation and the conditions of each case. ~Ddk001 $\square$

Uses

A great advantage of using this result is that one only have compute (for the most part) inverses modulo $p$ instead of higher powers. In fact, one can find inverses of large powers of primes using this result.

Additionally, one can use the Chinese Remainder Theorem to solve polynomial congruences of all moduli.

Example

Find the inverse of $107$ modulo $53^3$ .

Solution:

Let $y$ be the inverse.

Seeing a power of a prime as modulus reminds us of Hensel's Lemma for solving polynomial congruences. Let $f(y)=107y-1$ . We wish to solve $f(y) \equiv 0 \pmod {53^3}$ . Obviously, $107 \equiv 1 \pmod {53}$ , so $f(1) \equiv 0 \pmod {53}$ . By Hensel's Lemma, there exists a unique integer $t \in [0,53)$ such that $f(53t+1) \equiv 0 \pmod {53^2}$ , and $t$ is given by

$t=- \bar{f'(1)} \cdot (\frac{f(1)}{53})$

where $\bar{f'(1)}$ denotes the inverse of $f'(1)$ modulo $53$ (just $53$ , not $53$ to any power). Again, $107 \equiv 1 \pmod {53}$ , so since $f'(1) =107$ , $\bar{f'(1)}=1$ , so

$t= -1 \cdot \frac{106}{53}$

$=-2$

Therefore, we see that $f(-105) \equiv 0 \pmod {53^2}$ . We preform another lift. Again, there exists unique integer $t \in [0,53)$ such that $f(-105+53^2 \cdot t) \equiv 0 \pmod {53^3}$ , given by