Difference between revisions of "Hensel's Lemma"

Revision as of 15:17, 8 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

UNDER CONSTRUCTION

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)

Revision as of 20:59, 7 January 2025 (view source) Ddk001 (talk \| contribs) ← Older edit		Revision as of 15:17, 8 January 2025 (view source) Charking (talk \| contribs) m (Added stub to page) Newer edit →
Line 76:		Line 76:

	[[Category:Theorems]]		[[Category:Theorems]]
		+
		+	{{stub}}

Page

Toolbox

Search