Expansion of Integers in an Integer Base

This is pretty basic: all integers and even real numbers have a decimal expansion, (also, a decimal representation). For example, say, \(568 = 5\times 10^{2}+6\times 10^{1} + 8\times 10^{0}\). I do not believe that I ever came across a proof of that fact, although, for the integers at least, it is a direct consequence of the Euclidean Algorithm.

A positive integer \(a\) can be divided by \(10\): \(a = 10a_{1} + r_{0}\), \(0\le r_{1}\lt 10\), where \(r_{0}\) is going to be the last digit in the decimal expansion of \(a\). To obtain the penultimate digit, divide the first quotient \(a_{1}\) by \(10\): \(a_{1}=10a_{2}+r_{1}\), \(0\le r_{1}\lt 10\), so that

\(a = 10a_{1} + r_{0} = 10(10a_{2}+r_{1})+r_{0}= a_{2}10^{2}+r_{1}10^{1}+r_{0}10^{0}.\)

If \(a_{2} \lt 10\) we stop here, otherwise continue: \(a_{2}=10a_{3}+r_{2}\), with \(0\le r_{2}\lt 10\). Since \(\{a_{i}\}\) is a decreasing sequence of positive integers, it must be finite; the Euclidean algorithm stops when \(0\lt a_{n+1}=r_{n}\lt 10\), with the result that

\( \begin{array}{3,2} a &= 10(10\ldots (10(10r_{n} + r_{n-1})+r_{n-2})\ldots +r_{1})+r_{0} \\ &=r_{n}10^{n}+r_{n-1}10^{n-1}+\ldots +r_{1}10^{1}+r_{0}10^0 \\ &=r_{n}r_{n-1}\ldots r_{1}r_{0}, \end{array} \)

the latter being the decimal expansion of \(a\).

We - especially the "calculator generation" - are so used to thinking of integers in decimal terms that the decimal expansion is usually explained (re: positional numeration) but its existence is taken for granted; the Euclidean algorithm serves mostly as a tool for converting decimals to other bases. But obviously, the algorithm bearing Euclid's name has been annunciated centuries before the introduction (in Europe by Leonardo Fibonacci in 1202) of the decimal system.

Below I shall prove the existence and uniqueness of a representation in an integer base indepent of the Euclidean algorithm [Moll, pp. 17-18].

Theorem

Given \(a, b\in \mathbb{N}\), with \(b\gt 1\), there exist nonnegative integers \(x_{0}, x_{1},\ldots , x_{n}\) such that

\(a=x_{0}+x_{1}b+x_{2}b^{2}+\ldots + x_{n}b^{n},\)

with \(0\le x_{i}\lt b\) and \(x_{n}\ne 0\). This is the representation of \(a\) in base \(b\). The representation of \(a\) in base \(b\) is unique.

Proof

The proof is by induction on \(a\). The statement is clear for \(a=1\). Given a representation \(a=x_{0}+x_{1}b+x_{2}b^{2}+\ldots + x_{n}b^{n}\), for some \(a\), we are going to construct a representation for \(a+1\). There could be three cases. If \(x_{0}\lt b-1\), then

\(a+1=(x_{0}+1)+x_{1}b+x_{2}b^{2}+\ldots + x_{n}b^{n}\)

is the desired representation of \(a+1\). In the case \(x_{0}=b-1\), let \(j\) be the first index for which \(x_{j}\lt b-1\), if there is one. In this case,

\(a=(b-1)+(b-1)b+(b-1)b^{2}+\ldots +(b-1)b^{j-1}+x_{j}b^{j}+\ldots +x_{n}b^{n},\)

and then,

\( \begin{array}{3,2} a+1 &= 1+(b-1)(1+b+b^{2}+\ldots +b^{j-1}+x_{j}b^{j}+\ldots +x_{n}b^{n} \\ &=b^{j}+x_{j}b^{j}+\ldots +x_{n}b^{n} \\ &=(x_{j}+1)b^{j}+\ldots +x_{n}b^{n} \end{array} \)

is the desired representation. The final case is when \(j=n\), i.e., when

\(a = (b-1)(1+b+b^{2}\ldots +b^{n}) = b^{n+1}-1\).

In this case, \(a+1=b^{n+1}\). This completes the proof of existence.

To prove the uniqueness, assume on the contrary that there are two representations:

\(a=x_{0}+x_{1}b+x_{2}b^{2}+\ldots + x_{n}b^{n}\) and
\(a=y_{0}+y_{1}b+y_{2}b^{2}+\ldots + y_{m}b^{m}\)

Let \(j\) be the first index, for which \(x_{j}\ne y_{j}\). Assume, for example, that \(x_{j}\gt y_{j}\). Subtracting two representations, we obtain

\(0=(x_{j}-y_{j})b^{j}+ T, \)

where \(T\) (for a tail) is the sum of all the remaining differences, each containing a factor of at least \(b^{j+1}\) so that

\(0=(x_{j}-y_{j}) + T/b^{j} \equiv x_{j}-y_{j}\space (\mbox{mod}\space b)\).

But, since \(0\le x_{j}, y_{j}\lt b\), it must be that \(x_{j}=y_{j}\), contrary to the assumption that they are different.

References

  1. V. H. Moll, Numbers and Functions: From a Classical-Experimental Mathematician's Point of View, AMS, 2012

Related material
Read more...

  • Base (Binary, Decimal, etc.) Converter
  • Base Converter
  • Implementation of Base Conversion Algorithms
  • Conversion of Fractions in Various Bases
  • Scoring: the simplest of the impartial games
  • History of the Binary System
  • Calculation of the Digits of pi by the Spigot Algorithm of Rabinowitz and Wagon
  • Addition and Multiplication Tables in Various Bases
  • |Activities| |Contact| |Front page| |Contents| |Algebra|

    Copyright © 1996-2018 Alexander Bogomolny

    71923760