1.25: The Base b Representation of n

Definition \(\PageIndex{1}\)

Let \(b\ge 2\) and \(n>0\). We write \[\label{eq:1} n=\left[a_k,a_{k-1},\dotsc,a_1,a_0\right]_b \] if and only if for some \(k\ge 0\) \[n=a_kb^k+a_{k-1}b^{k-1}+\dotsb+a_1b+a_0\nonumber \] where \(a_i\in\{0,1,\dotsc,b-1\}\) for \(i=0,1,\dotsc,k\). \(\left[a_k,a_{k-1},\dotsc,a_1,a_0\right]\) is called a base \(b\) representation of \(n\).

Remark \(\PageIndex{1}\)

Base \(b\) is called \[\begin{aligned} binary \quad & \text{if }b=2, \\ ternary \quad & \text{if }b=3, \\ octal \quad & \text{if }b=8, \\ decimal \quad & \text{if }b=10, \\ hexadecimal \quad & \text{if }b=16.\end{aligned}\] If \(b\) is understood, especially if \(b=10\), we write \(a_ka_{k-1}\dotsm a_1a_0\) in place of \(\left[a_k,a_{k-1},\dotsc,a_1,a_0\right]_{10}\). In the case of \(b=16\), which is used frequently in computer science, the “digits” \(10\), \(11\), \(12\), \(13\), \(14\) and \(15\) are replaced by \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\), respectively.

For a fixed base \(b\ge 2\), the numbers \(a_i\in\{0,1,2,\dotsc,b-1\}\) in equation (1) are called the digits of the base \(b\) representation of \(n\). In the binary case \(a_i\in\{0,1\}\) and the \(a_i\)’s are called bits (binary digits).

Here are a few examples:

1. \(267=[5,3,1]_7\) since \(267 = 5 \cdot 7^2+3\cdot 7 +1\).
2. \(147=[1,0,0,1,0,0,1,1]_2\)since \(147=1\cdot 2^7+0\cdot 2^6+0\cdot 2^5+1\cdot 2^4+0\cdot 2^3+0\cdot 2^2+1\cdot 2+1\).
3. \(4879=[4,8,7,9]_{10}\) since \(4879 = 4\cdot 10^3+8\cdot 10^2 + 7\cdot 10 + 9\).
4. \(10705679=[A,3,5,B,0,F]_{16}\)since \(10705679=10\cdot 16^5+3\cdot 16^4+5\cdot 16^3+11\cdot 16^2+0\cdot 16+15\).
5. \(107056791=[107, 56, 791]_{1000}\)since \(107056791=107\cdot 1000^2+56\cdot 1000 +791\).

Theorem \(\PageIndex{1}\)

If \(b\ge 2\), then every \(n>0\) has a unique base \(b\) representation of the form \(n=\left[a_k,\dotsc,a_1,a_0\right]_b\) with \(a_k>0\).

Proof

Apply repeatedly the Division Algorithm as follows: \[\begin{aligned} n &=bq_0+r_0,\quad 0\le r_0<b \\ q_0 &=bq_1+r_1,\quad 0\le r_1<b \\ q_1 &=bq_2+r_2,\quad 0\le r_2<b \\ &\qquad\vdots \\ q_{k-1} &=bq_k+r_k,\quad 0\le r_k<b \\ q_k &=bq_{k+1}+r_{k+1},\quad 0\le r_{k+1}<b.\end{aligned}\] It is easy to see that if \(q_k>0\): \[n>q_0>q_1>\dotsm>q_k.\nonumber \] Since this cannot go on forever we eventually obtain \(q_\ell=0\) for some \(\ell\). Then we have \[q_{\ell-1}=b\cdot 0+r_\ell.\nonumber \] I claim that \(n=\left[r_\ell,r_{\ell-1},\dotsc,r_0\right]\) if \(\ell\) is the smallest integer such that \(q_\ell=0\). To see this, note that \[n=bq_0+r_0\nonumber \] and \[q_0=bq_1+r_1.\nonumber \] Hence \[\begin{aligned} n &=b\left(bq_1+r_1\right)+r_0 \\ n &=b^2q_1+br_1+r_0.\end{aligned}\] Continuing in this way we find that \[n=b^{\ell+1}q_{\ell}+b^\ell r_\ell+\dotsb+br_1+r_0.\nonumber \] And, since \(q_\ell=0\) we have \[\label{eq:2} n=b^\ell r_\ell+\dotsb+br_1+r_0, \] which shows that \[n=\left[r_\ell,\dotsc,r_1,r_0\right]_b.\nonumber \] To see that this representation is unique, note that from \(\eqref{eq:2}\) we have \[n=b\left(b^{\ell-1}r_\ell+\dotsb+r_1\right)+r_0,\quad 0\le r_0<b.\nonumber \] By the Division Algorithm it follows that \(r_0\) is uniquely determined by \(n\), as is the quotient \(q=b^{\ell-1}r_\ell+\dotsb+r_1\). A similar argument shows that \(r_1\) is uniquely determined. Continuing in this way we see that all the digits \(r_\ell,r_{\ell-1},\dotsc,r_0\) are uniquely determined.

Example \(\PageIndex{1}\)

1. We find the base \(7\) representation of \(1\),\(749\). \[\begin{aligned} 1749 &=249\cdot 7+6 \\ 249 &=35\cdot 7+4 \\ 35 &=5\cdot 7+0 \\ 5 &=0\cdot 7+5\end{aligned}\] Hence \(1749=[5,0,4,6]_7\).
2. We find the base \(12\) representation of \(19\),\(151\). \[\begin{aligned} 19,151 &=1595\cdot 12+11 \\ 1,595 &=132\cdot 12+11 \\ 132 &=11\cdot 12+0 \\ 11 &=0\cdot 12+11\end{aligned}\] \(\therefore 19,151=[11,0,11,11]_{12}\).
3. Find the base \(10\) representation of \(1\),\(203\). \[\begin{aligned} 1203 &=120\cdot 10+3 \\ 120 &= 12\cdot 10+0 \\ 12 &=1\cdot 10+2 \\ 1 &=0\cdot 10+1\end{aligned}\] \(\therefore 1203=[1,2,0,3]_{10}\).
4. Find the base \(2\) (binary) representation of \(137\). \[\begin{aligned} 137 &=2\cdot 68+1 \\ 68 &=2\cdot 34+0 \\ 34 &=2\cdot 17+0 \\ 17 &=2\cdot 8+1 \\ 8 &=2\cdot 4+0 \\ 4 &=2\cdot 2+0 \\ 2 &=2\cdot 1+0 \\ 1 &=2\cdot 0+1\end{aligned}\] \(\therefore 137=[1,0,0,0,1,0,0,1]_2\).

Exercise \(\PageIndex{1}\)

Generalize the following observations \[\begin{aligned} 3 &=[1,1]_2 \\ 7 &=[1,1,1]_2 \\ 15 &=[1,1,1,1]_2 \\ 31 &=[1,1,1,1,1]_2 \\ 63 &=[1,1,1,1,1,1]_2\end{aligned}\] Prove your generalization.

Hint

See Exercise 2.5

Exercise \(\PageIndex{2}\)

Generalize the following observation: \[\begin{aligned} 8 &=[2,2]_3 \\ 26 &=[2,2,2]_3 \\ 80 &=[2,2,2,2]_3 \\ 242 &=[2,2,2,2,2]_3\end{aligned}\] Prove your generalization.

Hint

See Exercise 2.5

Exercise \(\PageIndex{3}\)

Generalize Exercises \(\PageIndex{1}\) and \(\PageIndex{2}\) to an arbitrary base \(b\ge 2\).

Remark \(\PageIndex{2}\)

To find the binary representation of a small number, the following method is often easier than the above method:

Given \(n>0\) let \(2^{n_1}\) be the largest power of \(2\) satisfying \(2^{n_1}\le n\). Let \(2^{n_2}\) be the largest power of \(2\) satisfying \[2^{n_2}\le n-2^{n_1}.\nonumber \] Let \(2^{n_3}\) be the largest power of \(2\) satisfying \[2^{n_3}\le n-2^{n_1}-2^{n_2}.\nonumber \] Note that at this point we have \[0\le n-\left(2^{n_1}+2^{n_2}+2^{n_3}\right)<n-\left(2^{n_1}+2^{n_2}\right)<n-2^{n_1}<n.\nonumber \] Continuing in this way, eventually we get \[0=n-\left(2^{n_1}+2^{n_2}+\dotsb+2^{n_k}\right).\nonumber \] Then \(n=2^{n_1}+2^{n_2}+\dotsb+2^{n_k}\), and this gives the binary representation of \(n\).

Example \(\PageIndex{2}\)

Take \(n=137\). Note that \(2^1=2\), \(2^2=4\), \(2^3=8\), \(2^4=16\), \(2^5=32\), \(2^6=64\), \(2^7=128\), and \(2^8=256\). Using the above method we compute: \[\begin{aligned} 137-2^7 &=137-128=9, \\ 9-2^3 &=1, \\ 1-2^0 &=0.\end{aligned}\] So we have \[\begin{gathered} 137=2^7+9=2^7+2^3+1, \\ \therefore 137=2^7+02^6+02^5+02^4+2^3+02^2+0\cdot 2+1.\end{gathered}\] So \(137=[1,0,0,0,1,0,0,1]_2\).

Exercise \(\PageIndex{4}\)

Show how to use both methods to find the binary representation of \(455\).

Exercise \(\PageIndex{5}\)

Make a vertical list of the binary representation of the integers 1 to 16.