Unknown

100 3. Factors and Zeros

Verify that the unique solution of this is v G 4 (mod 9).
For the next step, let h = 2 and u = 4, so that f(u) = 18 and j’(u) = 8
and the congruence for v becomes

0 E 18 + S(v - 4) (mod 81)

or
8v - 14 (mod81).

This is a congruence of the form studied in Exercise 1.6.6. Since 8 and
81 are coprime, there is a unique solution modulo 81. By making use of
the Euclidean algorithm (Exercise 1.6.2) or otherwise, obtain the solution
v E 22 (mod 81).
For the final step, let h = 4 and u = 22. Show that this leads to the
congruence
0 E 486 + 44(v - 22) (mod 812)

or
44v E 482 (mod 812).
Obtain the solution v = 2695. Conclude that t2+2 z 0 (mod 3”) is satisfied
by t = 2695, and obtain the solution to the same congruence (mod 35) as
required.
Let us return to the general situation. Establish the following result:
Suppose 1 5 h < k < 2h, p is prime and f(t) is a polynomial over Z.
Suppose further that u% an integer for which

(i) f(u) E 0 (mod ph)

(ii) f’(u) $ 0 (mod p).

Then there is an integer w for which wf’(u) E 1 (mod p2h) and the number

v = u - wf(u) satisfies the congruence

f(v) - 0 (modp2h).

Why is the condition f’(u) $ 0 (mod p) imposed? To see that some

condition like (ii) is needed, verify that

t2 + t + 1 E 0 (mod 3) is solvable

P+t+1=0( mod 9) is not solvable.

This result is the heart of the proof of Hensel’s Lemma:

Let p be a prime and let f(t) be a polynomial over Z. Suppose ~1 is a

solution of the congruence f(t) - 0 (mod p) such that f’(u1) # 0 (mod p).

Then for each positive integer k, there is a solution uk of the congruence

f(t) = 0 (mod pk).

Solve the congruence t4 + t2 + t + 1 s 0 (mod 256). [Answer: 1491.