TAOCP 4.1 Exercise 28

Section 4.1: Positional Number Systems

Exercise 28. ▶ [**] $[M24]$ Show that every nonzero complex number of the form $a + bi$ where $a$ and $b$ are integers has a unique "revolving binary representation"

$$(1+i)^{e_0} + i(1+i)^{e_1} - (1+i)^{e_2} - i(1+i)^{e_3} + \cdots + i^r(1+i)^{e_r},$$

where $e_0 < e_1 < \cdots < e_r$. (Compare with exercise 27.)

Verified: yes
Solve time: 9m35s

---

Let

$$ R(e_0,\ldots,e_r) =(1+i)^{e_0}+i(1+i)^{e_1}-(1+i)^{e_2}-i(1+i)^{e_3} +\cdots+i^r(1+i)^{e_r}, \qquad e_0<\cdots<e_r. $$

We must prove that every nonzero Gaussian integer $z=a+bi$ admits a unique representation of this form.

The proof is most naturally obtained from Exercise 27. Recall that Exercise 27 shows that every positive integer has a unique binary representation

$$ n=2^{e_0}+2^{e_1}+\cdots+2^{e_r}, \qquad e_0<e_1<\cdots<e_r. $$

We shall reduce the present problem to that result.

Existence

Let

$$ z=a+bi\neq0. $$

Choose $m\ge0$ maximal such that $(1+i)^m\mid z$. Then

$$ z=(1+i)^m w, $$

where $w$ is not divisible by $1+i$.

A Gaussian integer is divisible by $1+i$ if and only if its real and imaginary parts have the same parity. Therefore the real and imaginary parts of $w$ have opposite parity. Hence

$$ w\equiv1 \pmod{1+i} \quad\text{or}\quad w\equiv i \pmod{1+i}. $$

Multiplying by a suitable power of $i$, we may write

$$ w=i^s u, \qquad s\in{0,1,2,3}, $$

where

$$ u\equiv1\pmod{1+i}. $$

Thus it suffices to represent every Gaussian integer congruent to $1$ modulo $1+i$.

Consider such a $u$. Since $u-1$ is divisible by $1+i$, write

$$ u=1+(1+i)v . $$

Now repeat the same procedure with $v$. At each step, if the current quotient is nonzero, it is either divisible by $1+i$ or congruent to $1$ or $i$ modulo $1+i$. Recording a digit only when the quotient is not divisible by $1+i$, we obtain

$$ u=\varepsilon_0+\varepsilon_1(1+i)+\varepsilon_2(1+i)^2+\cdots, $$

where each $\varepsilon_j\in{0,1,i}$.

The process terminates because division by $1+i$ decreases the norm by a factor $2$:

$$ N!\left(\frac{x}{1+i}\right)=\frac{N(x)}2. $$

Hence after finitely many steps the quotient becomes $0$, so only finitely many digits are nonzero.

Now let

$$ e_0<e_1<\cdots<e_r $$

be the positions of the nonzero digits. By construction the first nonzero digit is $1$. After a nonzero digit has occurred, the next nonzero digit must be the other residue class modulo $1+i$. Indeed, if

$$ x=\varepsilon +(1+i)y, \qquad \varepsilon\in{1,i}, $$

then $x-\varepsilon$ is divisible by $1+i$; dividing by $1+i$ interchanges the two nonzero residue classes $1$ and $i$ modulo $1+i$. Consequently the successive nonzero digits alternate

$$ 1,\ i,\ 1,\ i,\ \ldots . $$

When these digits are moved back to the original powers of $1+i$, each passage through a factor $1+i$ multiplies the coefficient by $i$. Therefore the coefficients attached to the successive nonzero terms are

$$ 1,\ i,\ i^2,\ i^3,\ldots , $$

that is,

$$ 1,\ i,\ -1,\ -i,\ 1,\ldots . $$

Hence

$$ u=(1+i)^{e_0} +i(1+i)^{e_1} -(1+i)^{e_2} -i(1+i)^{e_3} +\cdots +i^r(1+i)^{e_r}. $$

Multiplying by the initial factor $i^s(1+i)^m$ merely adds the constant $m$ to every exponent and rotates the coefficient cycle by $i^s$. Reindexing the exponents gives again a representation of the required revolving form. Thus every nonzero Gaussian integer possesses such a representation.

Uniqueness

Suppose that

$$ \sum_{k=0}^{r} i^k(1+i)^{e_k} = \sum_{\ell=0}^{t} i^\ell(1+i)^{f_\ell}, $$

with

$$ e_0<\cdots<e_r, \qquad f_0<\cdots<f_t. $$

Subtracting, we obtain a nontrivial relation

$$ \sum_{j\ge0} c_j(1+i)^j=0, $$

where each coefficient satisfies

$$ c_j\in{0,\pm1,\pm i}. $$

Let $m$ be the least index for which $c_m\neq0$. Then

$$ c_m+(1+i)q=0 $$

for some Gaussian integer $q$, hence

$$ 1+i\mid c_m. $$

But none of

$$ \pm1,\ \pm i $$

is divisible by $1+i$, since each has norm $1$ whereas $N(1+i)=2$.

This contradiction shows that no nontrivial relation exists. Therefore the revolving representation is unique.

Hence every nonzero Gaussian integer $a+bi$ has a unique representation

$$ (1+i)^{e_0} +i(1+i)^{e_1} -(1+i)^{e_2} -i(1+i)^{e_3} +\cdots +i^r(1+i)^{e_r}, \qquad e_0<e_1<\cdots<e_r. $$

$\square$