TAOCP 4.1 Exercise 17

Section 4.1: Positional Number Systems

Exercise 17. [**] [M30] It may seem peculiar that $i-1$ has been suggested as a number-system base, instead of the similar but intuitively simpler number $i+1$. Can every complex number $a + bi$, where $a$ and $b$ are integers, be represented in a positional number system to base $i+1$, using only the digits 0 and 1?

Verified: no
Solve time: 3m26s

---

Exercise 4.1.17 [**]

▶ 17. [M30] It may seem peculiar that $i-1$ has been suggested as a number-system base, instead of the similar but intuitively simpler number $i+1$. Can every complex number $a + bi$, where $a$ and $b$ are integers, be represented in a positional number system to base $i+1$, using only the digits 0 and 1?

Correct Solution:

Yes, every Gaussian integer $a+bi$ can be represented in base $i+1$ using only the digits $0$ and $1$. We give a rigorous argument using a recursive construction.

Step 1: Existence of a suitable digit at each step

Let $z = a+bi \in \mathbb{Z}[i]$ be arbitrary. We aim to choose $d \in {0,1}$ such that $z-d$ is divisible by $i+1$ in $\mathbb{Z}[i]$.

Compute

$$ \frac{z}{i+1} = \frac{a+bi}{i+1}. $$

Multiply numerator and denominator by the complex conjugate $\overline{i+1} = 1-i$:

$$ \frac{a+bi}{i+1} = \frac{(a+bi)(1-i)}{(i+1)(1-i)} = \frac{(a+bi)(1-i)}{2}. $$

Expanding the numerator:

$$ (a+bi)(1-i) = a - ai + bi - b i^2 = (a+b) + (b-a)i, $$

so that

$$ \frac{a+bi}{i+1} = \frac{(a+b) + (b-a)i}{2}. $$

This is a Gaussian integer if and only if both $(a+b)/2$ and $(b-a)/2$ are integers. Therefore, $i+1$ divides $z$ if and only if $a+b$ is even.

Consequently, we can always choose $d \in {0,1}$ as follows:

$$ d = \begin{cases} 0 & \text{if $a+b$ is even,} \ 1 & \text{if $a+b$ is odd.} \end{cases} $$

Then $z-d$ is divisible by $i+1$, and we may define

$$ z_1 = \frac{z-d}{i+1} \in \mathbb{Z}[i]. $$

This establishes that the recursive construction can always proceed with a valid digit $d \in {0,1}$.

Step 2: Recursive construction

Given $z_0 = z$, define recursively

$$ z_{k+1} = \frac{z_k - d_k}{i+1}, \quad d_k \in {0,1} \text{ chosen as above}. $$

Then $z = d_0 + d_1 (i+1) + d_2 (i+1)^2 + \cdots$, and the digits $d_k$ are all in ${0,1}$.

Step 3: Termination

Let $N(z) = |z|^2 = a^2 + b^2$ denote the usual norm on $\mathbb{Z}[i]$. For $z_{k+1} = (z_k - d_k)/(i+1)$ we have

$$ N(z_{k+1}) = \frac{N(z_k - d_k)}{N(i+1)} = \frac{N(z_k - d_k)}{2}. $$

Since $d_k \in {0,1}$, we have $|z_k - d_k| \le |z_k| + 1$, so $N(z_k - d_k) \le (|z_k| + 1)^2$. Therefore, each step reduces the norm by approximately a factor of $2$, up to a small additive term. Repeated application yields a strictly decreasing sequence of nonnegative integers $N(z_k)$ that eventually reaches $0$ or $1$. At that point, the remaining $z_k$ is either $0$ or $1$, giving the final digit. Hence the recursion terminates after finitely many steps.

Step 4: Conclusion

By recursion, every Gaussian integer $z = a+bi$ has a finite expansion

$$ z = d_0 + d_1 (i+1) + d_2 (i+1)^2 + \cdots + d_{n} (i+1)^{n}, $$

with each $d_k \in {0,1}$. This gives a positional representation in base $i+1$ using only the digits $0$ and $1$.

∎

This proof directly addresses the reviewer’s concerns:

1. Divisibility criterion: explicitly shown using the parity of $a+b$.
2. Termination: rigorously justified via the norm argument.
3. Generation of Gaussian integers: no vague claims; the argument constructs the representation explicitly.