1.4: Representations of Integers in Different Bases

\(\newcommand{\NN}{\mathbb N}\)
\(\newcommand{\RR}{\mathbb R}\)
\(\newcommand{\QQ}{\mathbb Q}\)
\(\newcommand{\ZZ}{\mathbb Z}\)
\(\newcommand{\Cc}{\mathcal C}\)
\(\newcommand{\Dd}{\mathcal D}\)
\(\newcommand{\Ee}{\mathcal E}\)
\(\newcommand{\Ff}{\mathcal F}\)
\(\newcommand{\Kk}{\mathcal K}\)
\(\newcommand{\Mm}{\mathcal M}\)
\(\newcommand{\Pp}{\mathcal P}\)
\(\newcommand{\ind}{\operatorname{ind}}\)
\(\newcommand{\ord}{\operatorname{ord}}\)

In this section, we show how any positive integer can be written in terms of any positive base integer expansion in a unique way. Normally we use decimal notation to represent integers, we will show how to convert an integer from decimal notation into any other positive base integer notation and vise versa. Using the decimal notation in daily life is more traditional probably only because we have ten fingers. (“What about our toes?” you cry. I don’t know. And apparently the Babylonians had \(30\) fingers on each hand, or \(15\) on each hand and each foot, since they used base \(60\).)

Notation An integer \(a\) written in base \(b\) expansion is denoted by \((a)_b\).

Theorem \(\PageIndex{1}\)

Let \(b\in\ZZ\) satisfy \(b>1\). Then \(\forall m\in\NN\), \(\exists l\in\NN\) and \(\exists a_1,\dots,a_l\in\ZZ\) such that \[\begin{aligned} m=a_lb^l+a_{l-1}b^{l-1}+\dots+a_1b+a_0,\\ 0\leq a_j<b\text{ for }j=0,1,\dots,l,\text{ and}\ \ \ \\ a_l\neq 0.\hskip2.5cm\end{aligned}\]

Proof

Fix an \(m\in\NN\). We start by dividing \(m\) by \(b\) and we get \[m=q_0b+a_0, \ \ \ 0\leq a_0 <b.\] If \(q_0\neq 0\) then we continue to divide \(q_0\) by \(b\) and we get \[q_0=q_1b+a_1, \ \ \ 0\leq a_1<b.\] We continue this process and hence we get \[\begin{aligned} q_1&=q_2b+a_2, \ \ \ 0\leq a_2<b,\\ &\ .\\ &\ .\\ &\ .\\ q_{l-2}&=q_{l-1}b+a_{l-1}, \ \ \ 0\leq a_{l-1}<b,\\ q_{l-1}&=0\cdot b+a_l, \ \ \ 0\leq a_l<b.\end{aligned}\] Note that the sequence \(q_0,q_1,\dots\) is a decreasing sequence of non-negative integers with a last term \(q_l\) that must be \(0\).

Now substituting the equation \(q_0=q_1b+a_1\) in \(m=q_0b+a_0\), we get \[m=(q_1b+a_1)b+a_0=q_1b^2+a_1b+a_0,\] Successively substituting the equations in \(m\), we get \[\begin{aligned} m&=q_2b^3+a_2b^2+a_1b+a_0,\\ &\ .\\ &\ .\\ &\ .\\ &=q_{l-1}b^l+a_{l-1}b^{l-1}+\dots+a_1b+a_0,\\ &= a_lb^l+a_{l-1}b^{l-1}+\dots+a_1b+a_0.\end{aligned}\] What remains to prove is that the representation is unique. Suppose now that \[m=a_lb^l+a_{l-1}b^{l-1}+\dots+a_1b+a_0=c_lb^l+c_{l-1}b^{l-1}+\dots+c_1b+c_0\] where if the number of terms is different in one expansion, we add zero coefficients to make the number of terms agree. Subtracting the two expansions, we get \[(a_l-c_l)b^l+(a_{l-1}-c_{l-1})b^{l-1}+\dots+(a_1-c_1)b+(a_0-c_0)=0.\] If the two expansions are different, then there exists \(0\leq j\leq l\) such that \(c_j\neq a_j\). As a result, we get \[b^j((a_l-c_l)b^{l-j}+\dots+(a_{j+1}-c_{j+1})b+(a_j-c_j))=0\] and since \(b\neq 0\), we get \[(a_l-c_l)b^{l-j}+\dots+(a_{j+1}-c_{j+1})b+(a_j-c_j)=0.\] We now get \[a_j-c_j=(a_l-c_l)b^{l-j}+\dots+(a_{j+1}-c_{j+1})b,\] and as a result, \(b\mid (a_j-c_j)\). Since \(0\leq a_j<b\) and \(0\leq c_j<b\), we get that \(a_j=c_j\). This is a contradiction and hence the expansion is unique.

Definition: Base \(b\) Expression

Given \(b\in\ZZ\) satisfying \(b>1\). For \(m\in\NN\), let \(\ell\in\NN\) and \(a_1,\dots,a_\ell\in\ZZ\) be as in the above theorem (Theorem 1.4.1). Then the base \(b\) expression for \(m\) is the sequences of digits \(m_b=a_\ell\dots a_1\). If \(b\ge10\), we often use some other single symbols to represent the possible values from \(10\) to \(b-1\) of the \(a_i\)’s. For example, \[\begin{aligned} 10&\leftrightsquigarrow A\\ 11&\leftrightsquigarrow B\\ 12&\leftrightsquigarrow C\\ &\text{ etc.}\end{aligned}\]

Base \(2\) representation of integers is called binary representation. Binary representation is useful for computers: the coefficients \(a_0,\dots,a_l\) of a binary representation all satisfy \(0\le aj<2\), hence they are \(0\) or \(1\). Thus to represent an integer on \(l\) wires, one can have each wire either have voltage \((1)\) or not \((0)\). (In fact, the word bit is a contraction of binary digit.)

Computer programmers also frequently use base \(8\) and base \(16\), called octal and hexadecimal or hex, respectively. The Babylonians used base \(60\), called sexagesimal.

Example \(\PageIndex{1}\)

To find the expansion of \(214\) base \(3\): we do the following \[\begin{aligned} 214&=3\cdot 71+1\\ 71&= 3\cdot 23+2\\ 23&= 3\cdot 7+2\\ 7&= 3\cdot 2+1\\ 2&= 3\cdot 0+2\\\end{aligned}\] As a result, to obtain a base \(3\) expansion of \(214\), we take the remainders of divisions and we get that \((214)_{10}=(21221)_3\).

Example \(\PageIndex{2}\)

To find the base \(10\) expansion, i.e., the decimal expansion, of \((364)_7\): We do the following: \(4\cdot 7^0+6\cdot 7^1+3\cdot 7^2=4+42+147=193\).

Exercise \(\PageIndex{1}\)

1. Convert \((7482)_{10}\) to base \(6\) notation.
2. Convert \((98156)_{10}\) to base \(8\) notation.
3. Convert \((101011101)_2\) to decimal notation.
4. Convert \((AB6C7D)_{16}\) to decimal notation.
5. Convert \((9A0B)_{16}\) to binary notation.