Difference between revisions of "Hensel's Lemma"

Revision as of 21:44, 9 January 2025

Hensel's Lemma is a important result in Number Theory for solving polynomial congruences.

Statement

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

(i) 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$ denote the inverse of $f(r)$ modulo $p$ .

(ii) 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$

(iii) 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 preformed 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 \codt p^{k-1}$ (Error compiling LaTeX. Unknown error_msg):

$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

$t = - \bar{f'(-105)} \cdot (\frac{f(-105)}{53^2})$

$f'(-105)$ is also $107$ , so $\bar{f'(-105)} = 1$ . We have $f(-105)= -105 \cdot 107 -1=-106^2= (-4) \cdot 53^2$ , so

$t = -1 \cdot (\frac{(-4) \cdot 53^2}{53^2}$

$=4$

Therefore, $f(4 \cdot 53^2-105) \equiv 0 \pmod {53^3}$ . We have

$y=\boxed{4 \cdot 53^2-105}$

$\square$

Note that we will use this exact result in the first practice problem.

Problems

Introductory

Intermediate

Let $x$ be the remainder when

$106! + (53!)^2$

is divided by $107 \cdot 53^3$ . Find the remainder when $x$ is divided by $1000$ . (Source and solution)

@@ Line 17: / Line 17: @@
 ==Proof==
-UNDER CONSTRUCTION
+As in the hypothesis, <math>r</math> is an integer such that <math>f(r) \equiv 0 \pmod {p^{k-1}}</math>. If <math>r'</math> satisfy <math>f(r') \equiv 0 \pmod {p^{k}}</math>, then we must have <math>r \equiv r' \pmod {p^{k-1}}</math> so <math>r'=r+t \cdot p^{k-1}</math> for some integer <math>t</math>.
+By the formula for [[Taylor Series]] (of point <math>x=a+b</math> around the point <math>x=a</math>),
+<cmath>f(a+b)=f(a) +f'(a) \cdot b + f''(a) \cdot \frac{b^2}{2!} + \cdot + f^{(n)} (a) \cdot {b^n}{n!}</cmath>
+We plug in <math>a=r</math> and <math>b=t \codt p^{k-1}</math>:
+<cmath>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}</cmath>
+The result for each case follow from the above equation and the conditions of each case. ~[[Ddk001]] <math>\square</math>
 ==Uses==

Page

Toolbox

Search