Proposition 8

Let $b$ be an integer $>1$. For each integer $k>0$ let $E_k$ be the lexicographic product (§ 2, no. 6) of the family $(J_h)_{0\leq h\leq k-1}$ of intervals all identical with $[0,b-1]$. For each $r=(r_0,r_1,\ldots,r_{k-1})\in E_k$, let

then the mapping $f_k$ is an isomorphism of the ordered set $E_k$ onto the interval $[0,b^k-1]$.

The proof is by induction on $k$. For $k=1$ it is an immediate consequence of the definitions. For each $r=(r_0,\ldots,r_{k-1},r_k)\in E_{k+1}$ put

Then the mapping $r\mapsto(\varphi(r),r_k)$ is an isomorphism of $E_{k+1}$ onto the lexicographical product of $E_k$ and $J=[0,b-1]$; this is immediate from the definitions. We may write

let us show that the relation $r<r'$ in $E_{k+1}$ implies $f_{k+1}(r)<f_{k+1}(r')$. Indeed, we have either $\varphi(r)<\varphi(r')$, or else $\varphi(r)=\varphi(r')$ and $r_k<r'_k$. In the first case, the inductive hypothesis implies that $f_k(\varphi(r))<f_k(\varphi(r'))$, and therefore (§ 4, no. 2, Proposition 2) $f_k(q(r'))\geq f_k(\varphi(r))+1$; consequently

since $r_k\leq b-1$ (no. 2, Proposition 3). If, on the other hand, $\varphi(r)=\varphi(r')$ and $r_k<r'_k$, it is clear that $f_{k+1}(r)<f_{k+1}(r')$. Now the inductive hypothesis shows that $f_k(\varphi(r))\leq b^k-1$, whence

It follows that $f_{k+1}$ is an isomorphism of $E_{k+1}$ onto a subset of the interval $[0,b^{k+1}-1]$; but this interval and $E_{k+1}$ have the same number of elements, namely $b^{k+1}$ (no. 3, Proposition 5); therefore $f_{k+1}$ is a bijection (§ 4, no. 2, Proposition 2, Corollary 4), and the proof is complete. ¶ We note now that for every integer $a$ we have $a < b^a$. This is proved by induction on $a$; the result is evident for $a = 0$, and the hypothesis $a < b^a$ implies $a + 1 \leqslant b^a < b \cdot b^a = b^{a+1}$ (no. 2, Proposition 3 and § 4, no. 2, Proposition 2). There is therefore a least integer $k$ such that $a < b^k$, and Proposition 8 then shows that there exists a unique finite sequence $(r_h)_{0 \leqslant h \leqslant k-1}$ such that $0 \leqslant r_h \leqslant b - 1$ for $0 \leqslant h \leqslant k - 1$ and

Furthermore, we must have $r_0 > 0$, for otherwise $a < b^{k-1}$ by virtue of Proposition 8. The expression is called the expansion to base $b$ of the integer $a$.

\* In all parts of mathematics which do not involve numerical computations, Proposition 8 is useful mainly when applied to a prime number $b$. \*

When the integer $b$ is small enough for this to be practicable, we may represent each integer $< b$ by a distinctive symbol called a digit. The digits which represent 0 and 1 are usually 0 and 1. Let $a$ be an integer and let $\sum_{h=0}^{k-1} r_h b^{k-h-1}$ be its expansion to base $b$. If the integer $k$ which appears in this expansion is sufficiently small for this to be practicable, it is usual to associate with the integer $a$ the succession of symbols obtained by writing $r_0 r_1 \ldots r_{k-2} r_{k-1}$ from left to right and then replacing each integer $r_i$ by the digit which represents it; the symbol so obtained is called the numerical symbol associated with $a$. One then often replaces $a$ by its numerical symbol in the terms and relations in which it appears.

For example, if C, Q, F, D are digits, the numerical symbols CQ, CQF, CQFD are respectively associated with $\mathrm{C}b + \mathrm{Q}$, $\mathrm{C}b^2 + \mathrm{Q}b + \mathrm{F}$, $\mathrm{C}b^3 + \mathrm{Q}b^2 + \mathrm{F}b + \mathrm{D}$.

It follows from Proposition 8 that the numerical symbol associated with an integer $a$ is unique, and that if $a < b^k$ it contains at most $k$ digits. Notice that the numerical symbol associated with the integer $b^k$ consists of the digit 1 followed by $k$ digits 0.

This system of representation of integers by numerical symbols is called the system of numeration to base $b$. In practical numerical computations, the following systems are used : (a) the system to base 2, or the dyadic system, in which the digits are 0 and 1; (b) the decimal system, in which the digits are $0$, $1$, $2$, $3$, $4$, $5 = 4 + 1$, $6 = 5 + 1$, $7 = 6 + 1$, $8 = 7 + 1$, $9 = 8 + 1$, and in which $b$ is the integer $9 + 1$ (whose numerical symbol in this system is therefore 10).

Since the Middle Ages the decimal system has been traditionally used in numerical calculations, and we shall use it in this series whenever we have occasion to write down an integer explicitly. We refer the reader to the part of this series devoted to numerical calculation for an account of methods for obtaining the numerical symbols associated with the sum, difference, product, and integral part of the quotient of two integers given by their numerical symbols.