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.
Contents
[hide]Statement
Suppose that is a polynomial function with integer coeficients and let
be a prime number. Also, let
be an arbitary integer with
. Suppose further that
be a solution to the congruence
. From here, there is three cases to consider:
(i) If is not congruent to
modulo
, then there exists a unique integer
such that
, given by
, where denote the inverse of
modulo
.
(ii) If , then
for all integers
(iii) If but
is not congruent to
modulo
, then
have no solutions with
Each time we bring up the exponent of , it is said that we preformed a lift.
Proof
As in the hypothesis, is an integer such that
. If
satisfy
, then we must have
so
for some integer
.
By the formula for Taylor Series (of point around the point
),
We plug in and
:
The result for each case follow from the above equation and the conditions of each case. ~Ddk001
Uses
A great advantage of using this result is that one only have compute (for the most part) inverses modulo 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 modulo
.
Solution:
Let be the inverse.
Seeing a power of a prime as modulus reminds us of Hensel's Lemma for solving polynomial congruences. Let . We wish to solve
. Obviously,
, so
. By Hensel's Lemma, there exists a unique integer
such that
, and
is given by
where denotes the inverse of
modulo
(just
, not
to any power). Again,
, so since
,
, so
Therefore, we see that . We preform another lift. Again, there exists unique integer
such that
, given by
is also
, so
. We have
, so
Therefore, . We have
Note that we will use this exact result in the first practice problem.
Problems
Introductory
Intermediate
Let be the remainder when
is divided by . Find the remainder when
is divided by
.
(Source and solution)