Unknown

3.4. Locating Integer Roots: Modular Arithmetic 99

and

(‘i’)+(L:)=( kT.1)

fork=1,3,5 ,..., p-2.

The induction step follows easily from

(1 + n)p - (1 + n) = ‘2 ( i ) nk + (np - n).

kc1

E.33. Hensel’s Lemma. In Exercise 4.11, we showed how to solve a

congruence to a prime power by starting with a solution modulo the prime

and then increasing the exponent by steps of 1. Taylor’s Theorem is the

basis of a more efficient method which allows us to solve the congruence in

successive stages in which the exponent is doubled. Suppose p” is a prime

power and the polynomial congruence to be solved is

f(t) 3 0 (modpk). (*I

Suppose h and k are positive integers such that 1 5 h < k 5 2h, andthat

a solution u is known to the congruence

f(t) q 0 (modpA).

Then any number of the form u + mph also satisfies this congruence. We

try to find a number v of this form which will satisfy (*). Thus, we can

think of u as a “first approximation” to a solution to (*).

Taylor’s Theorem can be employed to express f(v) in terms of f(u):

f(v) = f(u) + (v - 4f’W + (v - 42Kwv”w

+ (l/S)f”‘(u)(v - U) +. ..I.

If v is to satisfy (*) and v G u (mod ph), argue that we must have

0 q f(u) + (v - u)f’(~) (modpk).

Conversely, show that if we can determine v z u (mod ph) such that

0 G f(u) + (v - u)j’(u) (modp2h),

then v is a solution to (*).
Let us see how this can be used to solve the congruence

t2 + 2 G 0 (mod 243).

The congruence t2 + 2 - 0 ( mod 3) is satisfied by t = 1. Making the
substitution p = 3, h = 1, f(t) = t2 + 2, u = 1, we find that j(u) = 2,
f’(u) = 2 and the congruence for v becomes

0 E 3 + 2(v - 1) (mod 9).