next up previous
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 $ \mathbb {Z}$/pe$ \mathbb {Z}$ 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 $ \geq$ 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 $ \geq$ k + 1 since k $ \geq$ 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 $ \mathbb {Z}$/p$ \mathbb {Z}$. Let m be an inverse so that mf'(nk) = 1(mod p). We put bk = - mck and obtain the required condition. $ \qedsymbol$

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 $ \mathbb {Z}$/pe$ \mathbb {Z}$ 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 - $ \sum_{i>0}^{}$[n/pi]. In particular, if p is odd then the latter term goes to infinity with n.

Proof. Exercise. $ \qedsymbol$

It follows that only finitely many terms of the power series

log(1 - x) = - $\displaystyle \sum_{i\geq 0}^{}$% latex2html id marker 15024
$\displaystyle {\frac{x^i}{i+1}}$

survive in $ \mathbb {Z}$/pe$ \mathbb {Z}$ when we substitute x by a multiple of p. Thus we obtain a map

log : U1$\displaystyle \to$$\displaystyle \mathbb {Z}$/pe$\displaystyle \mathbb {Z}$

which in fact takes values in the ideal p$ \mathbb {Z}$/pe$ \mathbb {Z}$, which isomorphic to the additive group $ \mathbb {Z}$/pe - 1$ \mathbb {Z}$. 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$\displaystyle \mathbb {Z}$/pe$\displaystyle \mathbb {Z}$$\displaystyle \to$U1

by means of the usual power series

exp(x) = $\displaystyle \sum_{i\geq 0}^{}$% latex2html id marker 15048
$\displaystyle {\frac{x^i}{i!}}$

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$ \mathbb {Z}$/pe$ \mathbb {Z}$ which is in turn isomorphic to $ \mathbb {Z}$/pe - 1$ \mathbb {Z}$. We note in passing that a generator g of U1 of order pe - 1 corresponds to the generator p in p$ \mathbb {Z}$/pe$ \mathbb {Z}$ via the expression g = exp(p)!

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