Hensel's Lemma and Chinese Remainder Theorem?

Question

Hi,

I seem to be having problems know when/how to use Hensel's Lemma and the Chinese Remainder Theorem... Any tips? Good advice? My midterm is on Monday, and I just seem stuck!

Thanks!

Answer 1

Suppose f is a polynomial and you know a solution
to f(x) = 0(mod p). Hensel's Lemma can be used to
find solutions of, say, f(x) mod p².
I will state it at the end of this post.
Right now, let's give a couple of simple examples:
Let's solve x² = 2(mod 49).
We know 2 solutions mod 7: x = 3 and x = 4.
Let f(x) = x²-2.
We have f'(x) = 2x
f'(3) .ne. 0(mod 7)
So there is a unique integer t, 0 <= t <= 6 such
that (3 + 7t)²-2 = 0(mod 49).
7 + 42t = 0(mod 49)
1 + 6t = 0(mod 7).
So t = 1(mod 7)
and a solution is 10² = 100 = 2(mod 49).
Now the same is true if r = 4
and we have to solve
(4+7t)² -2 = 0(mod 49)
16 + 7t -2 = 0(mod 49)
14 + 7t = 0(mod 49)
2 + t = 0(mod 7)
t = 5 mod 7
and the solution is 4+35 = 39 = -10 mod 49.
So the solutions mod 49 are x = 10 and x = -10.
Here's an example of a problem I had to solve the
other day:
Find all solutions of f(x) = x^10 + 1 = 0(mod 25).
The solutions mod 5 are x = 2 and x = 3.
and f'(x) = 0(mod 5) in each case.
Next, f(2) = 0(mod 25) and 3^10+1 = 0(mod 25)
So each solution mod 5 yields 5 solutions mod 25:
The solutions are
x = 2,3,7,8,12,13,17,18,22 and 23(mod 25).

Chinese remainder theorem.
This says:
Let x = a(mod m)
and x = b(mod n)
If (m,n) = 1 then this system has a unique solution mod mn.
This result can be extended to more than 2 congruences
provided the moduli are relatively prime in pairs.
Simple example:
Find the solution of the system
x = 2(mod 5)
x = 3(mod 7)
Solution:
The first congruence yields x = 2+ 5t
So 2 + 5t = 3(mod 7)
5t = 1(mod 7)
t = 3(mod 7)
x = 2 + 5(3+7t) = 17 + 35t
x = 17(mod 35).
Did you know that the Chinese remainder theorem
can be used to multiply numbers and even
multiply them with no carrying?
Let's do an example, which will give more
practice in using the theorem.
Multiply 15*12.
We pick 2 or more distinct prime moduli whose
product is bigger than the product we seek.
Let's try m1 = 3, m2 = 7 and m3 = 11.
Write each number mod each of these
15............................... 12
0 1 4........................ 0 5 1
Now multiply the components together:
15*12
0 5 4.
So we seek a number such that
x = 0 mod 3
x = 5 mod 7
x = 4 mod 11.
Let's solve this system, for practice:
3t = 5(mod 7)
t = 4(mod 7)
x = 3(4+7t) = 12(mod 21)
x = 12 + 21u
12+ 21u = 4(mod 11)
1 - u = 4(mod 11)
u = 8(mod 11)
x = 12 + 21(8 + 3*5*11*v)
x = 180.
FINALLY,
Here is Hensel's Lemma:
A version of the lemma for p-adic fields is as follows. Let f(x) be a polynomial with integer coefficients, k an integer not less than 2 and p a prime number. Suppose that r is a solution of the congruence

f(r) \equiv 0 \pmod{p^{k-1}}.\,

If f'(r) \not\equiv 0 \pmod{p}, then there is a unique integer t, 0 ≤ t ≤ p-1, such that

f(r + tp^{k-1}) \equiv 0 \pmod{p^k}\,

with t defined by

tf'(r) \equiv -(f(r)/p^{k-1}) \pmod{p}.\,

If, on the other hand, f'(r) \equiv 0 \pmod{p}, and in addition, f(r) \equiv 0 \pmod{p^k}, then

f(r + tp^{k-1}) \equiv 0 \pmod{p^k}\,

for all integers t.

Also, if f'(r) \equiv 0 \pmod{p}\, and f(r) \not\equiv 0 \pmod{p^k}, then f(x) \equiv 0 \pmod{p^k}\, has no solution for any x \equiv r \pmod{p^{k-1}}.\,
Note: \equiv is the TeX equivalent of the congruence sign.