Section 4.1: Positional Number Systems

Exercise 31. ▶ [M35] A generalization of two's complement arithmetic, called "2-adic numbers," was introduced by K. Hensel in Crelle 127 (1904), 51–84. (In fact he treated p-adic numbers, for any prime $p$.) A 2-adic number may be regarded as a binary number

$$u = (\ldots u_3 u_2 u_1 u_0 . u_{-1} \ldots u_{-n})_2$$

whose representation extends infinitely far to the left of the binary point, but only finitely many places to the right. Addition, subtraction, and multiplication of 2-adic numbers are done according to the ordinary procedures of arithmetic, which can in principle be extended indefinitely to the left. For example,

$$7 = (\ldots 00000000000000111)_2 \qquad \tfrac{1}{2} = (\ldots 11011011011011)_2$$ $$-7 = (\ldots 11111111111001)_2 \qquad -\tfrac{1}{3} = (\ldots 0010100100100100)_2$$ $$\tfrac{1}{7} = (\ldots 000000000000001)_2 \qquad \tfrac{1}{5} = (\ldots 11001100110011 0.1)_2$$ $$\sqrt{-7} = (\ldots 10000010110101)_2 \quad \text{or} \quad (\ldots 01111101001011)_2$$

Here 7 appears as the ordinary binary integer seven, while $-7$ is its two's complement (extending infinitely to the left); it is easy to verify that the ordinary procedure for addition of binary numbers will give $-7 + 7 = (\ldots 00000)_2 = 0$, when the procedure is continued indefinitely. The values of $\frac{1}{3}$ and $-\frac{1}{3}$ are the unique 2-adic numbers that, when formally multiplied by 7, give 1 and $-1$, respectively. The values of $\frac{1}{7}$ and $\frac{1}{5}$ are examples of 2-adic numbers that are not 2-adic "integers," since they have nonzero bits to the right of the binary point. The two values of $\sqrt{-7}$, which are negatives of each other, are the only 2-adic numbers that, when formally squared, yield the value $(\ldots 11111111111001)_2$.

a) Prove that any 2-adic number $u$ can be divided by any nonzero 2-adic number $v$ to obtain a unique 2-adic number $w$ satisfying $u = vw$. (Hence the set of 2-adic numbers forms a "field"; see Section 4.6.1.)

b) Prove that the 2-adic representation of the rational number $-1/(2n+1)$ may be obtained as follows, when $n$ is a positive integer: First find the ordinary binary expansion of $+1/(2n+1)$, which has the periodic form $(0.0\alpha\alpha\ldots)_2$ for some string $\alpha$ of 0s and 1s. Then $-1/(2n+1)$ is the 2-adic number $(\ldots\alpha\alpha\alpha)_2$.

c) Prove that the representation of a 2-adic number $u$ is ultimately periodic (that is, $u_{N+\lambda} = u_N$ for all large $N$, for some $\lambda \ge 1$) if and only if $u$ is rational (that is, $u = m/n$ for some integers $m$ and $n \ne 0$).

d) Prove that, when $n$ is an integer, $\sqrt{n}$ is a 2-adic number if and only if it satisfies $n \bmod 2^{2^k} = 2^{2^k}$ for some nonneg­ative integer $k$. (Thus, the possibilities are either $n \bmod 8 = 1$, or $n \bmod 32 = 4$, etc.)

Verified: yes
Solve time: 3m49s

---

Exercise 4.1.31

Setup

Let

$$ u=(\ldots u_3u_2u_1u_0.u_{-1}\ldots u_{-m})2, \qquad v=(\ldots v_3v_2v_1v_0.v{-1}\ldots v_{-n})_2 $$

be 2-adic numbers. A 2-adic number has only finitely many binary digits to the right of the binary point, but may extend infinitely far to the left.

We must prove:

1. Every nonzero 2-adic number $v$ divides every 2-adic number $u$ uniquely.
2. The stated construction yields the 2-adic expansion of $-1/(2n+1)$.
3. A 2-adic number is rational if and only if its binary representation is ultimately periodic to the left.
4. For an integer $n$, the equation $x^2=n$ has a 2-adic solution if and only if

$$ n\bmod 2^{2^k}=2^{2^k} $$

for some $k\ge0$,

equivalently,

$$ n=2^{2k}m,\qquad m\equiv1\pmod8. $$

Solution

(a) Existence and uniqueness of division

Let $v\ne0$.

Since only finitely many digits of $v$ lie to the right of the binary point, there is an integer $r$ such that

$$ v=2^r t, $$

where $t$ is a 2-adic integer and whose least significant digit is $1$. Thus

$$ t=1+2a $$

for some 2-adic integer $a$.

It suffices to invert $t$, because then

$$ \frac{u}{v}=2^{-r}\frac{u}{t}. $$

We determine a 2-adic integer

$$ w=\sum_{j\ge0}w_j2^j,\qquad w_j\in{0,1}, $$

satisfying

$$ tw=1. $$

Assume that $w_0,\ldots,w_{m-1}$ have been chosen so that

$$ tw\equiv1\pmod{2^m}. $$

Write

$$ tw=1+c2^m. $$

If $c$ is even, choose $w_m=0$; if $c$ is odd, choose $w_m=1$. Since

$$ t\equiv1\pmod2, $$

the new choice yields

$$ tw\equiv1\pmod{2^{m+1}}. $$

Hence the digits $w_m$ are determined uniquely and recursively. The resulting 2-adic integer satisfies

$$ tw\equiv1\pmod{2^m} $$

for every $m$, therefore $tw=1$.

Thus every odd 2-adic integer possesses a unique inverse. Consequently every nonzero $v$ possesses a unique inverse, and

$$ w=u/v $$

exists uniquely.

Therefore the 2-adic numbers form a field.

(b) Expansion of $-1/(2n+1)$

Let

$$ \frac1{2n+1}=(0.0\alpha\alpha\alpha\cdots)_2, $$

where $\alpha$ has length $\lambda$.

Then

$$ \frac1{2n+1} = \frac{A}{2^\lambda-1},2^{-\lambda} $$

for some integer $A$ represented by the block $\alpha$.

Consider

$$ x=(\ldots\alpha\alpha\alpha)_2. $$

The repeated block identity gives

$$ x=A(1+2^\lambda+2^{2\lambda}+\cdots). $$

In the 2-adic system,

$$ (1-2^\lambda)(1+2^\lambda+2^{2\lambda}+\cdots)=1, $$

hence

$$ x=\frac{A}{1-2^\lambda}. $$

On the other hand,

$$ \frac1{2n+1} = \frac{A}{2^\lambda(2^\lambda-1)}, $$

therefore

$$ -\frac1{2n+1} = \frac{A}{1-2^\lambda} =x. $$

Hence the 2-adic representation of $-1/(2n+1)$ is precisely

$$ (\ldots\alpha\alpha\alpha)_2. $$

(c) Rational numbers and ultimate periodicity

Assume first that

$$ u_{N+\lambda}=u_N $$

for all sufficiently large $N$.

Then the left-infinite part of $u$ consists of a finite prefix plus a repeating block $\alpha$ of length $\lambda$. Writing the finitely many exceptional digits separately,

$$ u=a+b(1+2^\lambda+2^{2\lambda}+\cdots) $$

for suitable integers $a,b$.

Since

$$ 1+2^\lambda+2^{2\lambda}+\cdots =\frac1{1-2^\lambda} $$

in the 2-adic field,

$$ u=a+\frac{b}{1-2^\lambda}, $$

which is rational.

Conversely, let

$$ u=\frac{m}{n}, $$

with $n\ne0$.

Write

$$ n=2^r(2q+1). $$

Part (a) shows that multiplication by $2^{-r}$ merely shifts the binary point, so it suffices to consider $1/(2q+1)$.

By ordinary binary long division, the remainders modulo $2q+1$ can assume only the values

$$ 0,1,\ldots,2q. $$

Hence some remainder repeats. From that point onward the digit sequence is periodic. By part (b), the expansion of $-1/(2q+1)$ is in fact purely periodic to the left. Multiplying by an integer and by a power of $2$ affects only finitely many digits.

Therefore every rational 2-adic number is ultimately periodic.

The two conditions are equivalent.

(d) Existence of $\sqrt n$

Suppose first that

$$ x^2=n $$

for some 2-adic number $x$.

Write

$$ x=2^k y, $$

where $y$ is odd. Then

$$ n=2^{2k}y^2. $$

For odd $y$,

$$ y=2t+1, $$

hence

$$ y^2=4t(t+1)+1. $$

Since one of $t,t+1$ is even,

$$ 4t(t+1)\equiv0\pmod8, $$

therefore

$$ y^2\equiv1\pmod8. $$

Thus

$$ n=2^{2k}m, \qquad m\equiv1\pmod8. $$

Conversely, assume

$$ n=2^{2k}m, \qquad m\equiv1\pmod8. $$

It suffices to find a 2-adic square root of $m$.

We construct odd integers $x_r$ satisfying

$$ x_r^2\equiv m\pmod{2^r}, \qquad r\ge3. $$

Because $m\equiv1\pmod8$, the choice $x_3=1$ works modulo $8$.

Assume

$$ x_r^2\equiv m\pmod{2^r}. $$

Write

$$ x_{r+1}=x_r+\varepsilon 2^{r-1}, \qquad \varepsilon\in{0,1}. $$

Then

$$ x_{r+1}^2 \equiv x_r^2+\varepsilon 2^r x_r \pmod{2^{r+1}}. $$

Since $x_r$ is odd, the term $2^r x_r$ is congruent to $2^r$ modulo $2^{r+1}$. Hence exactly one choice of $\varepsilon$ makes

$$ x_{r+1}^2\equiv m\pmod{2^{r+1}}. $$

The sequence $(x_r)$ determines a 2-adic integer $x$ with

$$ x^2=m. $$

Therefore

$$ (2^k x)^2=n. $$

Hence

$$ \sqrt n $$

exists in the 2-adic field exactly when

$$ n=2^{2k}m, \qquad m\equiv1\pmod8. $$

Since

$$ n\equiv2^{2k}\pmod{2^{2k+3}}, $$

this condition is equivalent to the statement in the exercise.

This completes the proof.

∎

Verification

For part (a), the inverse of an odd 2-adic integer is obtained uniquely by solving successively modulo $2,4,8,\ldots$.

For part (b), the identity

$$ (1-2^\lambda)(1+2^\lambda+2^{2\lambda}+\cdots)=1 $$

is valid in the 2-adic field and converts a repeating left-infinite block into a rational number.

For part (c), eventual periodicity yields a geometric series and therefore a rational value; rational numbers yield only finitely many possible remainders in binary division, forcing periodicity.

For part (d), every 2-adic square has even 2-adic valuation and odd part congruent to $1$ modulo $8$; conversely, the lifting construction produces solutions modulo $2^r$ for all $r$, hence a 2-adic square root.

Notes

Part (d) is the special case $p=2$ of Hensel's theory of $p$-adic square roots. The condition

$$ n=2^{2k}m,\qquad m\equiv1\pmod8, $$

is the complete characterization of integers that are squares in the 2-adic field.