Next: 5 Factorisation and Certificates Up: 4 Primes and Composites Previous: 4.4 Compositeness Tests

4.5 Hensel's lemma

We conclude this section with a proof of the proposition 8. The group of units in /pe is of order pe - pe - 1 = pe - 1(p - 1), thus it is enough to find elements of order p - 1 and pe - 1 in this group. First we prove a result that will be useful in other contexts

Lemma 10 (Hensel's lemma)   Let f (T) = Td + a1Td - 1 + ... + ad be a (monic) polynomial with integer coefficients ai. Let n be an integer so that f (n) is divisible by p, and f'(n) = dnd - 1 + a1(d - 1)nd - 2 + ... + ad - 1 is not divisible by p. Then there is a sequence of integers nk for every k 1, so that n1 = n, nk + 1 - nk is divisible by pk and f (nk) is divisible by pk. Moreover, nk is uniquely determined modulo pk.

Proof. The proof closely mimics Newton's method of finding roots. Having already found nk we need to find nk + 1 = nk + bkpk so that f (nk + 1) is divisible by pk + 1. By the binomial expansion (or Taylor series!),

f (nk + bkpk) = f (nk) + bkpkf'(nk)(mod pk + 1)

using 2k k + 1 since k 1. We are given f (nk) = ckpk for some constant ck. Moreover, nk = n(mod p) so f'(nk) = f'(n)(mod p) is an invertible element of /p. Let m be an inverse so that mf'(nk) = 1(mod p). We put bk = - mck and obtain the required condition.

We now apply this to the polynomial f (T) = Tp - 1 - 1 and any integer n prime to p to conclude that there is an integer ne so that nep - 1 = 1(mod pe) (note that f'(T) = - Tp - 2(mod p)). This gives us the required elements of order p - 1 (since such exist modulo p). Moreover, we see that the units in /pe can be written as gau where g is an element of order (p - 1) and u = 1(mod pe). Let U1 be the group of elements of the latter kind. We will now apply log and exp in a suitable way to conclude the result.

Lemma 11
1. Let x be divisible by p then the power of p that divides xn/n is at least n - [logp(n)], where the latter term denotes the integral part of logp(n). In particular, this goes to infinity with n.
2. Let x be divisible by p, then the power of p that divides pn/n! is at least n - [n/pi]. In particular, if p is odd then the latter term goes to infinity with n.

Proof. Exercise.

It follows that only finitely many terms of the power series

log(1 - x) = -

survive in /pe when we substitute x by a multiple of p. Thus we obtain a map

log : U1/pe

which in fact takes values in the ideal p/pe, which isomorphic to the additive group /pe - 1. Elementary manipulations of the power series combined with the binomial theorem and the fact that all but finitely many terms are zero can be used to show that log(1 + x . y + x + y) = log(1 + x) + log(1 + y). Similarly, for p odd we obtain a map

exp : p/peU1

by means of the usual power series

exp(x) =

which satisfies exp(x + y) = exp(x) . exp(y). We also check by direct substitution that log(exp(x)) = x and vice versa. It follows that the group U1 is isomorphic to the group p/pe which is in turn isomorphic to /pe - 1. We note in passing that a generator g of U1 of order pe - 1 corresponds to the generator p in p/pe via the expression g = exp(p)!

Next: 5 Factorisation and Certificates Up: 4 Primes and Composites Previous: 4.4 Compositeness Tests
Kapil Hari Paranjape 2002-10-20