1.6: The Base b Representation of n
- Page ID
- 83340
In this chapter we show how the Division Algorithm is related to a concept touched on since grade school mathematics.
Recall that the decimal representation of a positive integer \(a\) is given by \(a =a_{n-1}a_{n-2}\cdots a_1a_0\) where \[\label{decimalrep} a = a_{n-1}10^{n-1} + a_{n-2}10^{n-2} + \cdots + a_110 + a_0\] and the digits \(a_{n-1},a_{n-2},\dots,a_1,a_0\) are in the set \(\{0,1,2,3,4,5,6,7,8,9\}\) with \(a_{n-1}\neq 0\). In this case we say that the integer \(a\) is an \(n\)-digit number or that \(a\) is \(n\) digits long.
For example, the numerals in “682” are understood to mean six hundred eighty-two, because the locations of 6, 8, and 2 (in the “hundreds’ place”, “tens’ place”, and “ones’ place”) indicate the number \(6 \cdot 100 + 8\cdot 10 + 2\).
In this chapter we will justify the claim that every positive integer has a decimal representation. However, we will do so in a more general setting.
Let \(b\ge 2\) and \(n>0\). We write \[\label{eq:base} 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\).
Base \(b\) is referred to as \[\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]_{b}\). 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 \(\eqref{eq:base}\) 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:
- \(267=[5,3,1]_7\) since \(267 = 5 \cdot 7^2+3\cdot 7 +1\).
- \(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\).
- \(4879=[4,8,7,9]_{10}\) since \(4879 = 4\cdot 10^3+8\cdot 10^2 + 7\cdot 10 + 9\).
- \(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\).
- \(107056791=[107, 56, 791]_{1000}\)since \(107056791=107\cdot 1000^2+56\cdot 1000 +791\).
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}\] Note that in every step we always divide by \(b\). In the first line, we divide \(n\) by \(b\), and then in each line after the first, what we divide by \(b\) is the quotient of the previous line; we then use the resulting quotient for the next line.
From the repeated division it is not difficult to see that as long as \(q_k>0\), it is true that \[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 \] We claim that \(n=\left[r_\ell,r_{\ell-1},\dotsc,r_0\right]_b\) 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: base b again} 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 equation \(\eqref{eq: base b again}\) 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.
We can use the idea from the proof of Theorem \(\PageIndex{1}\), repeated applications of the Division Algorithm, to express numbers in an an arbitrary base. Following are some examples.
- 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\).
- 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}\).
- 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}\).
- 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\).
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\).
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+0\cdot2^6+0\cdot2^5+0\cdot2^4+2^3+0\cdot2^2+0\cdot 2+1.\end{gathered}\] So \(137=[1,0,0,0,1,0,0,1]_2\).
Exercises
Generalize the following observations \[\begin{aligned} 1 &=[1]_2 \\ 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}\] by noticing a pattern in the numbers on the left-hand sides and conjecturing a formula for the number that has \(n\) 1’s in its binary representation. Prove your generalization.
(Hint: See Exercise 1.3.8.)
Generalize the following observation: \[\begin{aligned} 2 &=[2]_3\\ 8 &=[2,2]_3 \\ 26 &=[2,2,2]_3 \\ 80 &=[2,2,2,2]_3 \\ 242 &=[2,2,2,2,2]_3\end{aligned}\] by noticing a pattern in the numbers on the left-hand sides and conjecturing a formula for the number that has \(n\) 2’s in its ternary representation. Prove your generalization.
(Hint: See Exercise 1.3.8.)
Generalize Exercises \(\PageIndex{1}\) and \(\PageIndex{2}\) to an arbitrary base \(b\ge 2\).
Show how to use both methods to find the binary representation of \(455\).
Make a vertical list of the binary representation of the integers 1 to 16.
Find the decimal representation of each of the following numbers.
- \([5,3,6,2]_7\);
- hexadecimal numbers FEEDAFACE and BADBEEF.
Following the technique of Example \(\PageIndex{1}\), find the representations of 12345 in (i) base 3 and (ii) base 8. For both parts (i) and (ii), show your work with the same level of detail as Example \(\PageIndex{1}\).
Find the base-7 representation of the number \([1,2,3,4,5,6,7,8]_9\).
Prove that if \(a\in\mathbb{N}\) is an \(n\)-digit number, then \(n={\mbox{\) (a) \(}}+1\). Here \(\log\) means logarithm to base 10. Thus \({\mbox{\) (a) \(}}+1\) is a formula for the number of digits in \(a\).
(Hint: to prove the equation, show that if equation \(\eqref{decimalrep}\) holds with \(a_{n-1}\neq 0\) then \(10^{n-1}\le a<10^n\). Then apply the \(\log\) to all terms of this inequality. This is allowed since \(\log\) is an increasing function on the set of positive real numbers.)
Use the previous exercise to determine the number of digits in the decimal representation of the number \(2^{3321928}\).
(Hint: recall that \(\log(x^y)=y\log(x)\) when \(x\) and \(y\) are positive.)
Recall that \(\log_b(a)\) means the logarithm of \(a\) with base \(b\). Can you adapt the ideas from Exercise \(\PageIndex{9}\) to find a formula for the number of digits in the base \(b\) representation of \(a\)?