How to Compute the 5-adic Expansion of 1/2; or: Hensel’s Lemma and (Non-Analytic) Newton Iteration.

Abstract.
In this post, we consider the quest of computing the 5-adic expansion of 1/2. We begin with introducing p-adic integers and numbers, and discussing when certain polynomials with coefficients in the integers have zeroes in the p-adic integers. This question is closely related to Hensel’s lemma, which can be proven using an algebraic version of Newton’s iteration. We use this to compute approximations of rational numbers in the p-adics, and consider which p-adic numers have an eventually periodic expansion.

Today, I want to discuss three topics: $p$ -adic integers and numbers, Hensel’s Lemma as well as Newton iteration. Three topics which, on the first glance, seem to have nothing in common. But nonetheless, there is a tight relation between them.

The $p$ -adic numbers.

Let us begin with the $p$ -adic numbers. They are a non-achrimedean analogue to the real numbers, whence we want to discuss the real numbers first. There are many different constructions of the real numbers. We pick a certain one, namely construction as a completion of the rational numbers. For that, consider the archimedean distance $d_\infty(x, y) = |x - y|$ respectively the archimedean absolute value $\displaystyle |x| = \begin{cases} x & \text{if } x \ge 0, \\ -x & \text{if } x < 0. \end{cases}$ Recall that a sequence $(a_n)_{n\in\N}$ is said to be convergent with limit $a \in \Q$ if for every $\varepsilon > 0$ , there exists some $n_0 \in \N$ with $d_\infty(a_n, a) < \varepsilon$ for all $n \ge n_0$ . Note that every convergent series is a Cauchy sequence, i.e. it satisfies $\displaystyle \forall \varepsilon > 0 \; \exists N \in \N \; \forall n, m \ge N : d_\infty(a_n, a_m) < \varepsilon.$ But not every Cauchy sequence in $\Q$ converges. One reason to use the real numbers is to add limits of Cauchy sequences, so that every Cauchy sequence (with coefficients in $\Q$ ) converges. More precisely, consider the set of Cauchy sequences, $C$ ; this is an $\Q$ -subspace of $\Q^\N$ , the space of all functions $\N \to \Q$ (i.e. all sequences). Consider the subspace $c$ of sequences converging to $0 \in \Q$ ; note that $c \subseteq C$ . Therefore, we can consider the quotient $\R := C / c$ ; $\Q$ embeds via the diagonal embedding, i.e. $q \in \Q$ maps to $(n \mapsto q) + c \in C / c = \R$ . One quickly checks that $\R$ is a ring, and that every non-zero element is in fact invertible, i.e. it is a field. Moreover, one quickly checks that the canonical order $\le$ on $\Q$ extends to $\R$ ; this allows to define $d_\infty(x, y)$ and $\abs{x}$ for $x, y \in \R$ in the same manner as for rational numbers. Moreover, one sees that all Cauchy sequences in $\R$ actually converge.

The $p$ -adic numbers can be constructed in a very similar way. Fix a prime number $p$ , and condider the $p$ -adic valuation on $\Q$ , defined by $\displaystyle \nu_p : \Q^* \to \Z, \qquad p^t \frac{a}{b} \mapsto t$ if $a, b \in \Z$ are not divisible by $p$ . Moreover, set $\nu_p(0) := \infty$ . Then, we can define the $p$ -adic absolute value $\abs{\bullet}_p : \Q \to \Q$ , $z \mapsto p^{-\nu_p(z)}$ ; then $\abs{z}_p = 0$ if, and only if, $z = 0$ ; we have that the strict triangle inequality $\displaystyle \abs{x + y}_p \le \max\{ \abs{x}_p, \abs{y}_p \} \le \abs{x}_p + \abs{y}_p$ is satisfied; and we have that $\abs{x y}_p = \abs{x}_p \abs{y}_p$ ; here, $x,y, z \in \Q$ are arbitrary. Such absolute values which satisfy the strict triangle inequality $\abs{x + y}_p \le \max\{ \abs{x}_p, \abs{y}_p \}$ are called non-archimedean absolute values.

Remark.

In fact, one can show that these $p$ -adic absolute values together with the above Archimedean absolute value are all absolute values on $\Q$ up to equivalence; here, we say that two absolute values $\abs{\bullet}_i, \abs{\bullet}_j$ are equivalent if there exists some number $t > 0$ with $\abs{z}_i = \abs{z}_j^t$ for all $z \in \Q$ .

Now let us continue with the $p$ -adic numbers. We can define Cauchy sequences and the notion of convergence as above, by replacing $d_\infty(x, y)$ by $d_p(x, y) := \abs{x - y}_p$ . As above, we obtain that $\Q$ has a completion with respect to $d_p$ which forms a field, denoted by $\Q_p$ . This is the field of $p$ -adic numbers. Also, $d_p$ and $\abs{\bullet}_p$ extend onto $\Q_p$ . As opposed to the case of the real numbers, the image of $d_p$ resp. $\abs{\bullet}_p$ do not change; the reason is that $\nu_p$ is a discrete valuation, i.e. attains only integers. Actually, this field $\Q_p$ has several interesting properties, which we want to collect.

Theorem.

For every $x, y \in \Q_p$ , $\abs{x + y}_p \le \max\{ \abs{x}_p, \abs{y}_p \} \le \abs{x}_p + \abs{y}_p$ .

The set $\{ x \in \Q_p \mid \abs{x}_p \le 1 \}$ is a subring of $\Q_p$ ; denote this subring by $\Z_p$ .

For any $B \in \R_{>0}$ , we have that $\{ x \in \Q_p \mid \abs{x} \le B \}$ and $\{ x \in \Q_p \mid \abs{x} < B \}$ are both open and closed in $\Q_p$ . In particular, $\Z_p$ is both open and closed.

We have that $\displaystyle \Z_p = \{ z \mid \exists (z_n)_n \text{ sequence in } \Z : \lim z_n = z \}.$

The ring $\Z_p$ is local with maximal ideal $\frakm_p := \{ x \in \Q_p \mid \abs{x}_p < 1 \}$ , and $\Z_p / \frakm_p \cong \Z/p\Z$ . In fact, $\Z_p$ is a discrete valuation ring.

The series $\sum_{n=0}^\infty a_n$ with $a_n \in \Q_p$ converges if, and only if, $\lim_{n\to\infty} a_n = 0$ .

Every non-zero element $z \in \Q_p^*$ can be written uniquely in the form $z = \sum_{n=k}^\infty a_n p^n$ , where $a_n \in \{ 0, \dots, p - 1 \}$ for all $n$ , $k = \nu_p(z)$ and $a_k \neq 0$ .

For every $n \in \N$ , $\Z_p / \frakm_p^n \cong \Z/p^n\Z$ .

If $\Q_p$ is equipped with the topology induced by the metric $d_p$ , then $\Z_p$ is the maximal compact subring of $\Q_p$ .

Proof.

Let $(x_n)_n$ , $(y_n)_n$ sequences in $\Z$ with $\lim x_n = x$ , $\lim y_n = y$ . Then, for every $n$ , $\max\{ \abs{x_n}_p, \abs{y_n}_p \} - \abs{x_n + y_n}_p \ge 0$ . Now $\Q_p$ is a topological ring, and $\abs{\bullet}_p$ is continuous, whence the result follows from applying $\lim_{n\to\infty}$ .

From (a), we see that this set is closed under addition. That it is closed under multiplication is clear, and $0, 1$ are contained in it as well.

Write $B = p^{-t + \varepsilon}$ with $t \in \Z$ and $0 \le \varepsilon < 1$ . Now $\abs{x}_p \le B \Leftrightarrow \abs{x}_p \le p^{-t} \Leftrightarrow \abs{x}_p < p^{-t + 1}$ , and $\displaystyle \abs{x}_p < B \Longleftrightarrow \begin{cases} \abs{x}_p \le B & \text{if } \varepsilon > 0, \\ \abs{x} \le p^{-t - 1} & \text{if } \varepsilon = 0. \end{cases}$

Let $(z_n)_n$ be a sequence of elements in $\Z$ which converges with respect to $d_p$ . Then $\abs{z_n}_p \le 1$ for all $n \in \N$ as $\nu_p(z_n) \ge 0$ ; as $\abs{\bullet}_p$ is continuous, $\abs{\lim z_n}_p = \lim \abs{z_n}_p \le 1$ .
Conversely, let $z \in \Z_p$ and let $(z_n)_n$ be a sequence of elements in $\Q$ with $\lim z_n = z$ . Now $\Z_p$ is open; therefore, there exists some $n_0$ with $\abs{z_n}_p \le 1$ for all $n \ge n_0$ . Without loss of generality, we can assume that $n_0 = 0$ , i.e. all $z_n$ lie in $\Z_p \cap \Q$ . Moreover, we can assume that $z_n \neq 0$ for all $n$ . We want to construct a sequence $(a_n)_n$ in $\Z$ with $\lim a_n = \lim b_n$ . For that, write $z_n = \frac{x_n}{y_n}$ with $x_n, y_n \in \Z$ , where $y_n$ is not divisible by $p$ . Let $\tilde{y}_n \in \{ 0, \dots, p^n - 1 \}$ be such that $y_n \tilde{y}_n \equiv 1 \pmod{p^n}$ and set $b_n := x_n \tilde{y}_n$ ; moreover, write $y_n \tilde{y}_n = 1 + c_n p^n$ with $c_n \in \Z$ . Then $\displaystyle b_n - a_n = b_n (1 - \tilde{y}_n y_n) = -b_n c_n p^n,$ whence $Formula does not parse: \bas{b_n - a_n} \le p^{-n}$ . Therefore, one obtains that $\lim a_n = \lim b_n = z$ .

One quickly checks using 1. that $\frakm_p$ is closed under addition. It is clearly also closed under multiplication by elements of $\Z_p$ , and contains 0; therefore, it is an ideal. Now consider the map $\Z \to \Z_p / \frakm_p$ ; clearly, $p \in \frakm_p$ , whence $p \Z$ is contained in the kernel of this map. But $1$ is not contained in the kernel, as $1 \not\in \frakm_p$ ; therefore, $\Z_p / \frakm_p$ contains a copy of $\Z/p\Z$ . To see that this is everything, let $x + \frakm_p \in \Z_p / \frakm_p$ ; let $(x_n)_n$ be a sequence in $\Z$ with $\lim x_n = x$ . Let $n_0$ be such that for all $n \ge n_0$ , $d_p(x_n, x) < 1$ ; then $x_n - x \in \frakm_p$ , whence $x + \frakm_p = x_n + \frakm_p$ . But $x_n + \frakm_p$ is contained in the copy of $\Z/p\Z$ .

Clearly, if the series converges, we must have that $\lim a_n = 0$ .
Now, conversely, assume that $\lim a_n = 0$ . We show that $(b_n)_n$ with $b_n = \sum_{k=0}^n a_k$ is a Cauchy series. For that, let $\varepsilon > 0$ be given. Choose $N$ such that for all $n \ge N$ , $\abs{a_n}_p < \varepsilon$ . Now, if $n, m \ge N$ with $n \ge m$ , we have that $\displaystyle \abs{b_n - b_m}_p = \abs{\sum_{k=m}^n a_k}_p \le \max\{ \abs{a_m}_p, \dots, \abs{a_n}_p \} < \varepsilon$ by 1., what we had to show.

First, for any choice of the $k$ ’s and $a_n$ ’s, we obtain an element $z = \sum_{n=k}^\infty a_n p^n$ in $\Q_p$ . Now assume that $\sum_{n=k}^\infty a_n p^n = \sum_{n=k}^\infty b_n p^n$ with $a_n, b_n \in \{ 0, \dots, p - 1 \}$ . Assume that there exists some $t$ with $a_t \neq b_t$ , and further assume that $t$ is chosen to be minimal under this condition, i.e. $a_n = b_n$ for all $n < t$ . Then $0 = \sum_{n=t}^\infty (a_n - b_n) p^n$ . Multiplying with $p^{-t}$ gives $0 = z := \sum_{n=0}^\infty (a_{n+t} - b_{n+t}) p^n$ with $a_t - b_t \in \{ -p + 1, \dots, -2, -1, 1, 2, \dots, p - 1 \}$ . Moreover, $z \in \Z_p$ , and $z + \frakm_p = (a_t - b_t) + \frakm_p$ . But now $a_t - b_t \not\in \frakm_p$ , whence $z + \frakm_p \neq 0 + \frakm_p$ . But by construction $z = 0$ , a contradiction. Therefore, the representations $\sum_{n=k}^\infty a_n p^n$ are unique.
We have to show that every element in $\Q_p$ can be written in this way. For that, let $z \in \Q_p^*$ ; now $z' := z p^{\nu_p(z)}$ satisfies $\abs{z'}_p = 1$ ; in particular, $z' \in \Z_p \setminus \{ 0 \}$ . We have to show that we can write $z' = \sum_{n=0}^\infty a_n p^n$ with $a_0 \neq 0$ . For that, let $(z_n)_n$ be a sequence in $\Z$ with $\lim z_n = z$ ; without loss of generality, we can assume that $\abs{z - z_n}_p \le p^{-n-1}$ for every $n$ . Then we also have $\abs{z_n - z_m}_p \le p^{-n-1}$ for every $m \ge n$ , whence $z_n \equiv z_m \pmod{p^{n+1}}$ . Therefore, we can choose $a_n \in \{ 0, \dots, p - 1 \}$ inductively such that $\sum_{t=0}^n a_t p^t \equiv z_n \pmod{p^{n+1}}$ , and we obtain that $z = \lim z_n = \lim \sum_{t=0}^n a_t p^t = \sum_{n=0}^\infty a_n p^n$ . Finally, since $0 = \nu_p(\sum_{n=0}^\infty a_n p^n) = \min\{ n \mid a_n \neq 0 \}$ (which follows from the strict triangle inequality), it follows that $a_0 \neq 0$ .

Clearly, $\frakm_p^n = \{ x \in \Q_p \mid \nu_p(x) \ge n \}$ ; therefore, using 7., we see that every residue class in $\Z_p / \frakm_p^n$ is uniquely described by $\sum_{t=0}^{n-1} a_n p^n + \frakm_p$ , where $a_n \in \{ 0, \dots, p - 1 \}$ . Hence, $\abs{\Z_p / \frakm_p^n} = p^n$ . Now, as in the proof of 5., we see that $\Z/p^n\Z$ injects into $\Z_p / \frakm_p^n$ , whence this injection is in fact a bijection. Thus $\Z_p / \frakm_p^n \cong \Z/p^n\Z$ .

Let $R$ be any compact subring of $\Q_p$ and $x \in R$ . If $\abs{x}_p > 1$ , then $\abs{x^n}_p \to \infty$ for $n \to \infty$ . Hence, $R$ is unbounded, a contradiction.
Hence, it is left to show that $\Z_p$ is compact. For that, it suffices to show that any sequence in $\Z_p$ has at least one accumulation point. Let $(x_n)_n$ be any sequence in $\Z_p$ . We claim that for any $n$ , there exists some $z_n \in \Z$ such that $z_n + \frakm_p^n$ contains infinitely many elements of the sequence. For $n = 0$ this is clear for any choice of $z_n$ ; hence, assume that this is the case for some $n$ . Now $z_n + \frakm_p^n = \bigcup_{i=0}^{p-1} (z_n + i p^n) + \frakm_p^{n+1}$ ; now there must be some $i \in \{ 0, \dots, p - 1 \}$ such that infinitely many of the $x_n$ ’s lie in $(z_n + i p^n) + \frakm_p^{n+1}$ (otherwise, only finitely many can lie in $z_n + \frakm_p^n$ ); set $z_{n+1} := z_n + i p^n$ . We see that $(z_n)_n$ is a Cauchy sequence, whence $z = \lim z_n \in \Z_p$ exists. Now by construction, $z$ is an accumulation point of $(x_n)_n$ . Therefore, $\Z_p$ is compact.

□

Before we continue, we want to explore another construction of $\Z_p$ which is completely algebraic. For that, we need the projective limit in the category of rings:

Definition.

Let $(I, \le)$ be a directed set and for every $i \in I$ , let $R_i$ be a ring. Assume that for every $i, j \in I$ with $i \le j$ there exists a homomorphism $\phi_{ij} : R_j \to R_i$ such that for all $i, j, k$ with $i \le j \le k$ , we have $\phi_{ik} = \phi_{ij} \circ \phi_{jk}$ , and we have $\phi_{ii} = \id_{R_i}$ . Such a tuple $((I, \le), (R_i)_i, (\phi_{ij})_{ij})$ is called a projective system. $\displaystyle \xymatrix{ R_k \ar[dd]_{\phi_{ik}} \ar[dr]^{\phi_{jk}} & \\ & R_j \ar[dl]^{\phi_{ij}} \\ R_i & }$ A projective limit of $((I, \le), (R_i)_i, (\phi_{ij})_{ij})$ is a ring $R$ together with homomorphisms $\pi_i : R \to R_i$ such that $\pi_j = \pi_i \circ \phi_{ij}$ if $i \le j$ , which satisfies the following universal property:
If $R'$ is any other ring and $\pi'_i : R \to R_i$ any other family of ring homomorphisms with $\pi_j = \pi_i \circ \phi_{ij}$ whenever $i \le j$ , there exists a unique homomorphism $\psi : R' \to R$ with $\pi_i \circ \psi = \pi'_i$ for all $i \in I$ . $\displaystyle \xymatrix{ R' \ar@{->}[r]^{\exists! \psi} \ar[dr]_{\pi'_i} & R \ar[d]^{\pi_i} \\ & R_i }$

We have the following, classical result:

Theorem.

For every projective system $((I, \le), (R_i)_i, (\phi_{ij})_{ij})$ of rings, there exists a projective limit which is unique up to unique isomorphism; i.e., for any two projective limits $(R, (\pi_i)_i)$ and $(R', (\pi'_i)_i)$ there exists a unique isomorphism $\psi : R' \to R$ such that $\pi_i \circ \psi = \pi'_i$ for all $i$ .
Moreover, a projective limit can be constructed as $\displaystyle R := \biggl\{ (r_i)_i \in \prod_{i \in I} R_i \;\biggm|\; \forall (i, j) \in {\le} : \psi_{ij}(r_j) = r_i \biggr\},$ where $\pi_i$ is the restriction of the canonical projection $\prod_{j \in I} R_j \to R_i$ to the subset $R$ .
□

Definition.

Let $((I, \le), (R_i)_i, (\phi_{ij})_{ij})$ be a projective system. Define the projective limit of it as any projective limit, and denote it by $\varprojlim_{i \in I} R_i$ .

We choose $I = \N$ with the usual order, and let $R_n := \Z/p^n\Z$ . Then, if $n \le m$ , one has the projection $\phi_{nm} : \Z/p^m\Z \to \Z/p^n\Z$ , $x + p^m\Z \mapsto x + p^n\Z$ . Hence, we can define $\hat{\Z}_p := \varprojlim_{n\in\N} R_n$ . Now this definition coincides with the old one; this can be seen using $\displaystyle \hat{\Z}_p = \{ (a_n)_n \mid a_n \in \{ 0, \dots, p^n - 1 \}, \; a_{n+1} \equiv a_n \pmod{p^n} \};$ then, the map $\displaystyle \Z_p \to \hat{\Z}_p, \qquad \sum_{n=0}^\infty a_n p^n \mapsto \biggl( \sum_{t=0}^{n-1} a_t p^t \biggr)_n$ is obviously an isomorphism.

Hensel’s Lemma.

Hensel’s Lemma can be formulated in a very algebraic way. All rings in this section are commutative and unitary.

Definition.

Let $R$ be a ring and $\fraka$ an ideal of $R$ . We say that $\fraka$ is nilpotent if $\fraka^n = 0$ for some $n \in \N$ . We say that $\fraka$ is a nilideal if every $x \in \fraka$ is nilpotent, i.e. if for every $x \in \fraka$ there is some $n_x \in \N$ with $x^{n_x} = 0$ .

Note that in Noetherian rings, nilideals are already nilpotent, since ideals generated by finitely many nilpotent elements are always nilpotent. (Note that our rings are commutative. Otherwise it won’t work.)

Proposition (Hensel's Lemma).

Let $R$ be a ring and $\fraka$ a nilideal in $R$ . Let $f \in R[x]$ and $a \in R$ such that $f(a) \in \fraka$ and $f'(a) + \fraka \in (R / \fraka)^*$ . Then there exists a unique $b \in R$ with $a - b \in \fraka$ and $f(b) = 0$ .

Proof (Part I).

First, assume that both $b$ and $b'$ satisfy $a - b, a - b' \in \fraka$ and $f(b) = 0 = f(b')$ . Using $t := b' - b$ , we see that $0 ={} & f(b') = f(b + t) = f(b) + f'(b) t + e t^2 \\ {}={} & (b' - b) ( f'(b) + e (b' - b) )$ for some $e \in R$ using Taylor expansion. Since $f'(b) + e (b' - b) + \fraka = f'(b) + \fraka = f'(a) + \fraka$ is a unit in $R / \fraka$ , there exist some $a \in R$ , $c \in \fraka$ with $a (f'(b) + e (b' - b)) = 1 + c$ . How $c$ is nilpotent, whence $(1 + c) \sum_{n=0}^\infty (-c)^n = 1$ , i.e. $1 + c \in R^*$ . But this means that $f'(b) + e (b' - b) \in R^*$ , whence $b' - b = 0$ . This shows uniqueness.
Moreover, we want to show that it suffices to require that $\fraka$ is nilpotent. Cosider the subring $R'$ of $R$ which is the smallest (unitary) subring containing the coefficients of $f$ and $a$ , and some fixed $b \in R$ with $f'(a) b - 1 \in \fraka$ . This ring is clearly finitely generated, whence Noetherian, and $\fraka' := \fraka \cap R'$ is a nilideal in $R'$ as well. Since $R'$ is Noetherian, $\fraka'$ is in fact nilpotent. Moreover, $f'(a) + \fraka' \in (R' / \fraka')^*$ since $f'(a) b - 1 \in \fraka'$ . Hence, it suffices to prove the lemma for $(R', \fraka')$ instead of $(R, \fraka)$ .
□

We will complete the proof later. First, let us discuss some implications of this result. Consider the ring $R = \Z/p^n\Z$ and $\fraka = p^m R$ , where $m > 0$ . Then clearly $\fraka$ is nilpotent in $R$ , whence we can apply Hensel’s lemma to this situation. Assume that $f \in \Z[x]$ is a polynomial and $a \in \Z$ with $f(a) \equiv 0 \pmod{p^m}$ ; if then $f'(a) \not\equiv 0 \pmod{p}$ , there exists a unique $b \in R$ with $f(b) = 0$ and $b \equiv a \pmod{p^m}$ . Doing this construction for $m = 1$ and all $n \in \N$ , we obtain a sequence $(b_n)_n$ of elements with $b_n \in \{ 0, \dots, p^n - 1 \}$ and $b_{n+1} \equiv b_n \pmod{p^n}$ , i.e. we obtain an element of $\hat{\Z}_p = \Z_p$ !

In particular, let $a \in \Z$ be any element with $p \nmid a$ . Consider $f := a x - 1 \in \Z[x]$ . Now there exists some $b, c \in \Z$ with $a b + c p = 1$ ; therefore, $f(b) \equiv 0 \pmod{p}$ . But this implies that there exists a unique $z \in \Z_p$ with $f(z) = 0$ and $z \equiv b \pmod{p}$ . (Since $b$ is unique modulo $p$ , it follows that $z$ is uniquely defined by $f(z) = 0$ , i.e. by $a z = 1$ .) Hence, we have shown that any integer $a$ is invertible in $\Z_p$ if $p \nmid a$ . But how to compute $z$ ? We will discuss this later; for now, note that we can use the Extended Euclidean Algorithm to find $b_n, c_n \in \Z$ with $a b_n + c_n p^n = 1$ ; then $b_n \equiv z \pmod{p^n}$ , i.e. we can approximate $z$ up to arbitrary precision.

What about $p \mid a$ ? In that case, $\frac{1}{a} \not\in \Z_p$ : if $a$ would have an inverse in $\Z_p$ , say $b \in \Z_p$ , then we would have $0 \equiv a \cdot b \equiv 1 \pmod{p}$ , a contradiction. Therefore, we get:

Proposition.

We have that $\displaystyle \Z_p \cap \Q = \biggl\{ \frac{a}{b} \in \Q \;\biggm|\; a, b \in \Z, \; p \nmid b \biggr\}.$
□

Newton Iteration.

In the last section, we ignored two points: first, how to prove existence in Hensel’s lemma, and second, how to compute this element in a constructive way. We want to fix this now. For this, we describe how Newton’s method works in arbitrary rings!

Let $f \in R[x]$ be a polynomial, $\fraka \subseteq R$ a nilpotent ideal, and $a \in R$ such that $f(a) \in \fraka$ and $f'(a) + \fraka \in (R / \fraka)^*$ . Fix some $\hat{a} \in R$ with $f'(a) \hat{a} - 1 \in \fraka$ , and consider the sequence $\displaystyle x_0 := a, \qquad x_{n+1} := x_n - \hat{a} f(x_n), \quad n \in \N.$ We claim that $f(x_n) \in \fraka^{n+1}$ for all $n \in \N$ ; since $\fraka$ is nilpotent, this means that the sequence becomes stationary eventually and gives a root of $f$ . Moreover, we claim that $x_n - x_{n-1} \in \fraka^n$ , whence $x_n - a \in \fraka$ for all $n$ .

Assume that this is true for some $n$ , i.e. we have $f(x_n) \in \fraka^{n+1}$ . Then $x_{n+1} = x_n - \hat{a} f(x_n)$ . Now $f(x_n) \in \fraka^{n+1}$ , whence $x_{n+1} - x_n \in \fraka^{n+1}$ . To show that $f(x_{n+1}) \in \fraka^{n+2}$ , we again use the Taylor expansion; by it, $f(x_{n+1}) ={} & f(x_n - \hat{a} f(x_n)) \\ {}={} & f(x_n) - f'(x_n) (\hat{a} f(x_n)) + e \hat{a}^2 f(x_n)^2 \\ {}={} & f(x_n) (1 - f'(x_n) \hat{a}) + e \hat{a}^2 f(x_n)^2$ for some $e \in R$ . Now $1 - f'(x_n) \hat{a} \in \fraka$ , whence $f(x_n) (1 - f'(x_n) \hat{a}) \in \fraka^{n+2}$ . Moreover, $f(x_n)^2 \in (\fraka^{n+1})^2 \subseteq \fraka^{n + 2}$ . Combining this gives $f(x_{n+1}) \in \fraka^{n+2}$ .

Therefore, the proof of Hensel’s lemma is completed. Moreover, we obtained an algorithm to refine an approximation of $\frac{1}{a} \in \Z_p$ without using the Extended Euclidean Algorithm: as soon as $\hat{a} \in \Z$ with $a \hat{a} \equiv 1 \pmod{p}$ is known, we can compute $\frac{1}{a}$ modulo $\frakm_p^n$ by applying the Newton iteration $x \mapsto x - \hat{a} f(x) = x - \hat{a} (a x - 1) = x (1 - \hat{a} a) + \hat{a} a$ only $n - 1$ times. Moreover, we can start with some intermediate result, say $\frac{1}{a}$ modulo $p^m$ , to compute $\frac{1}{a}$ modulo $p^n$ (with $n > m$ ) in at most $n - m$ iterations (which each need one multiplication and one addition modulo $p^n$ ). This is considerably faster than applying the Extended Euclidean Algorithm for $a$ and $p^n$ .

So, What About $\frac{a}{b}$ in $\Z_p$ ?

Assume that $p \nmid b$ ; then we know that $\frac{a}{b} \in \Z_p$ . Consider the polynomial $f := b x - a \in \Z[x]$ ; clearly, $f(\frac{a}{b}) = 0$ in $\Z_p$ , and $f'(\frac{a}{b}) = b$ is a unit in $\Z_p$ . Therefore, we can use the methods from above to compute $\frac{a}{b} \in \Z_p$ .

First, we need an approximation of $\frac{a}{b}$ modulo $p$ . For that, use the Extended Euclidean Algorithm to compute $c, c' \in \Z$ with $b c + p c' = 1$ ; then $a c$ satisfies $(a c) b \equiv a \pmod{p}$ , i.e. $\frac{a}{b} + \frakm_p = a c + \frakm_p$ .

Set $a_0 := a c \mod p$ and $\displaystyle a_{n+1} := a_n - c (b a_n - a) \mod p^{n+2} = a_n (1 - c b) + c a \mod p^{n+2},$ $n \ge 0$ . Then, by the above, $a_n + \frakm_p^{n+1} = \frac{a}{b} + \frakm_p^{n+1}$ . Hence, this allows to approximate $\frac{a}{b}$ up to an error of $\frakm_p^n$ in $n - 1$ iterations; we only need to perform the Extended Euclidean Algorithm once (to get a starting value), and from that, we can refine the approximation by applying a linear map.

As an example, let us consider $\frac{1}{2}$ in $\Z_5$ , i.e. $a = 1$ , $b = 2$ and $p = 5$ . Clearly, $3 \cdot 2 - 1 \cdot 5 = 1$ , whence we get $c = 3$ . Hence, $a_0 = 3$ . Now $1 - c b = -5$ and $c a = 3$ , whence $a_{n+1} = 3 - 5 a_n \mod 5^{n+2}$ , $n \in \N$ . We rapidly get $a_0 ={} & 3, \\ a_1 ={} & 13 = 2 \cdot 5 + 3, \\ a_2 ={} & 63 = 2 \cdot 5^2 + 2 \cdot 5 + 3, \\ a_3 ={} & 313 = 2 \cdot 5^3 + 2 \cdot 5^2 + 2 \cdot 5 + 3, \\ a_4 ={} & 1563 = 3 + 2 \cdot \sum_{n=1}^4 5^n, \\ a_5 ={} & 7813 = 3 + 2 \cdot \sum_{n=1}^5 5^n, \\ a_6 ={} & 39063 = 3 + 2 \cdot \sum_{n=1}^6 5^n, \\ a_7 ={} & 195313 = 3 + 2 \cdot \sum_{n=1}^7 5^n, \\ a_8 ={} & 976563 = 3 + 2 \cdot \sum_{n=1}^8 5^n, \\ a_9 ={} & 4882813 = 3 + 2 \cdot \sum_{n=1}^9 5^n, \\ a_{10} ={} & 24414063 = 3 + 2 \cdot \sum_{n=1}^10 5^n, \\ \vdots\;\; &$ Hence, it seems that $\displaystyle a_n = 3 + 2 \cdot \sum_{i=1}^n 5^i = 3 + 2 \cdot 5 \cdot \sum_{i=0}^{n-1} 5^i = 3 + \tfrac{5}{2} (5^n - 1),$ i.e. we have $\displaystyle \frac{1}{2} = 3 + \sum_{n=1}^\infty 2 \cdot 5^n \in \Z_5.$ And indeed: $\displaystyle 2 \cdot \biggl( 3 + \sum_{n=1}^\infty 2 \cdot 5^n \biggr) = 2 + 4 \cdot \sum_{n=0}^\infty 5^n = 1$ since $\displaystyle -1 = (p - 1) \sum_{n=0}^\infty p^n \in \Z_p.$ Note that $-1 = (p - 1) \sum_{n=0}^\infty p^n$ follows from the fact that $\nu_p(p) < 0$ , whence $\sum_{n=0}^\infty p^n$ converges in $\Z_p$ (see the theorem); this is a geometric series, whence its value is $\frac{1}{1 - p}$ . Hence, if we multiply by $p - 1$ , we obtain $-1$ .

Finally, let us consider another example, namely $\frac{432}{1234}$ in $\Z_{17}$ , i.e. $a = 432$ , $b = 1234$ , $p = 17$ ; then $(-5) b + 363 p = 1$ , i.e. $c = -5$ . Hence, we obtain $a_0 := a c \mod p = 16$ and $\displaystyle a_{n+1} = (1 - c b) a_n + c a \mod 17^{n+2} = 6171 a_n - 2160 \mod 17^{n+2},$ $n \in \N$ . We then obtain $a_0 ={} & 16, \\ a_1 ={} & 50 = 16 + 2 \cdot 17, \\ a_2 ={} & 1784 = 16 + 2 \cdot 17 + 6 \cdot 17^2, \\ a_3 ={} & 65653 = 16 + 2 \cdot 17 + 6 \cdot 17^2 + 13 \cdot 17^3, \\ a_4 ={} & 483258 = 16 + 2 \cdot 17 + 6 \cdot 17^2 + 13 \cdot 17^3 + 5 \cdot 17^4, \\ a_5 ={} & 13261971 = 16 + 2 \cdot 17 + 6 \cdot 17^2 + 13 \cdot 17^3 + 5 \cdot 17^4 \\ {}+{} & 9 \cdot 17^5, \\ a_6 ={} & 182224954 = 16 + 2 \cdot 17 + 6 \cdot 17^2 + 13 \cdot 17^3 + 5 \cdot 17^4 \\ {}+{} & 9 \cdot 17^5 + 7 \cdot 17^6, \\ a_7 ={} & 1413240973 = 16 + 2 \cdot 17 + 6 \cdot 17^2 + 13 \cdot 17^3 + 5 \cdot 17^4 \\ {}+{} & 9 \cdot 17^5 + 7 \cdot 17^6 + 3 \cdot 17^7, \\ a_8 ={} & 64195057942 = 16 + 2 \cdot 17 + 6 \cdot 17^2 + 13 \cdot 17^3 + 5 \cdot 17^4 \\ {}+{} & 9 \cdot 17^5 + 7 \cdot 17^6 + 3 \cdot 17^7 + 9 \cdot 17^8, \\ a_9 ={} & 1012898069918 = 16 + 2 \cdot 17 + 6 \cdot 17^2 + 13 \cdot 17^3 + 5 \cdot 17^4 \\ {}+{} & 9 \cdot 17^5 + 7 \cdot 17^6 + 3 \cdot 17^7 + 9 \cdot 17^8 + 8 \cdot 17^9, \\ a_{10} ={} & 13108861472612 = 16 + 2 \cdot 17 + 6 \cdot 17^2 + 13 \cdot 17^3 + 5 \cdot 17^4 \\ {}+{} & 9 \cdot 17^5 + 7 \cdot 17^6 + 3 \cdot 17^7 + 9 \cdot 17^8 + 8 \cdot 17^9 + 6 \cdot 17^{10}, \\ \vdots\;\; &$ This can be continued a long time, without seeing any pattern.

One would expect that the sequence of digits evenutally gets (eventually) periodic, as it happens with the decimal expansion of rational numbers. For that, assume that we know $\frac{a}{b} = p^t \frac{a'}{b'}$ , where $a', b'$ are coprime and not divisible by $p$ , and $b' > 0$ . Now let $\ell$ be the order of $p$ in the multiplicative group $\Z/b'\Z$ ; hence, it is the smallest non-negative rational number with $b' \mid (p^\ell - 1)$ . Then $\frac{a}{b} = p^t a' \frac{p^\ell - 1}{b'} \frac{1}{p^\ell - 1}$ . Now, $\displaystyle \frac{1}{p^\ell - 1} = -\sum_{n=0}^\infty p^{\ell n}$ by the geometric series (as above), whence $\displaystyle \frac{a}{b} = a' \frac{p^\ell - 1}{b'} \cdot \sum_{n=0}^\infty p^{\ell n + t}.$ Moreover, write $\frac{a'}{b'} = \frac{a''}{b'} + a'''$ with $a''' \in \Z$ such that $0 \le a'' < b'$ . Then $a' \frac{p^\ell - 1}{b'} = \frac{a'' (p^\ell - 1)}{b'} + a''' (p^\ell - 1)$ , and $0 \le \frac{a'' (p^\ell - 1)}{b'} < p^\ell$ . Set $x := \frac{a'' (p^\ell - 1)}{b'}$ ; then, if we write $x = \sum_{i=0}^{\ell - 1} x_i p^i$ , we see that $\displaystyle \frac{a}{b} = a''' + \sum_{n=0}^\infty \sum_{i=0}^{\ell - 1} a_i p^{\ell n + i + t} = a''' + \sum_{n=0}^\infty a_{\ell \mod n} p^{\ell + t}.$ We are left to consider the $a'''$ part. In case $a''' > 0$ , the $p$ -adic expansion of $a'''$ has finite length, whence adding it does not change the periodicity of $\frac{a}{b}$ . But what if $a''' < 0$ ?

Lemma.

Let $x = \sum_{n=0}^\infty a_n p^n \in \Z_p$ , where $0 \le a_n < p$ . Then $\displaystyle -x = 1 + \sum_{n=0}^\infty (p - 1 - a_n) p^n.$

Proof.

Clearly, $\displaystyle \sum_{n=0}^\infty a_n p^n + \sum_{n=0}^\infty (p - 1 - a_n) p^n = (p - 1) \sum_{n=0}^\infty p^n = -1 \in \Z_p,$ whence adding $1$ results in the statement.
□

Therefore, the $p$ -adic expansion of $a'''$ is periodic if $a''' < 0$ , with almost all $p$ -adic digits being $p - 1$ . Now, we can conclude with the fact that the sum of two periodic $p$ -adic expansions is periodic.

Conversely, assume that $x = x' + \sum_{n=0}^\infty a_{n \mod m} p^n \in \Z_p$ with $x' \in \Z$ and $a_0, \dots, a_{m-1} \in \{ 0, \dots, p - 1 \}$ ; we claim that $x \in \Q$ . Clearly, without loss of generality, we can assume that $x' = 0$ . But then, if we set $x'' := \sum_{i=0}^{m-1} a_i p^i \in \Z$ , $\displaystyle x = \sum_{n=0}^\infty \sum_{i=0}^{m-1} a_i p^{m n + i} = x'' \cdot \sum_{n=0}^\infty p^{m n} = \frac{x''}{1 - p^m} \in \Q.$ Hence, we proved:

Proposition.

An element $x = \sum_{n=t}^\infty a_n p^n \in \Q_p$ with $0 \le a_n < p$ lies in $\Q$ if, and only if, there exists some $m, m' \in \N$ such that for all $i \in \N$ , $a_{m' + i} = a_{m' + i + m}$ .
□

Finally, note that the order of 17 in $\Z/1234\Z$ is $\phi(1234) = 616$ ; hence, the period length of $\frac{432}{1234}$ is probably 616. We would have had to compute a high amount of $p$ -adic digits of $\frac{432}{1234}$ to see this.

Tags: Hensel's lemma, Newton iteration, p-adic integers

This entry was posted on Saturday, February 6th, 2010 at 22:03 Europe/Berlin and is filed under Algebra, Number Theory. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.