Number Theory - Elliptic Curves: Number Theory and Cryptography - page 471

x k (mod p m ) for all k for all m ≥ 1. Since x m ≡ ≥ m , the base p expansions

m must agree through the p m− 1 term. Therefore, the
sequence of integers x m determines an expression of the form

for all x k with k ≥

∞

a n p n ,

n =0

where

m − 1

a n p n (mod p m ) x m ≡

n =0

for all m . In other words, the sequence of integers determines a p -adic inte-
ger. Conversely, the partial sums of a p -adic integer determine a sequence of
integers satisfying (A.3).
Let's use these ideas to show that − 1 is a square in the 5-adic integers. Let
x 1 =2,so

x 1 ≡− 1(mod .
Suppose we have defined x m such that

x 2 m ≡−

m ) .

1(mod

Let x m +1 = x m + b 5 m ,where

≡ − 1 − x 2 m
2 · 5 m x m

b (mod 5) .

Note that x 2 m ≡− 1(mod5 m ) implies that the right side of this last congru-
ence is defined mod 5. A quick calculation shows that

x 2 m +1 ≡− 1(mod

m +1 ) .

x m (mod 5 m )for

Since (A.3) is satisfied, there is a 5-adic integer x with x ≡

all m .Moreover,

x 2

m )

≡− 1(mod

for all m . This implies that x 2 = 1.

In general, this procedure leads to the following very useful result.

−

THEOREM A.2 (Hensel's Lemma)
Let f ( X ) be a polynomial with coe cients that are p-adic integers and suppose
x 1 is an integer such that

f ( x 1 ) ≡ 0(mod p ) .

If

f ( x 1 ) ≡ 0(mod p ) ,