Theorem 5.2.1.1.
Let \(b\in\NN-\{1\}\) and \(a\in\NN\cup\{0\}\text{.}\) Then there are \(n\in\NN\cup\{0\}\) and \(a_i\in\ZZ_b\) where \(0\le i\le n\) such that
\begin{equation*}
a=\sum_{i=0}^n a_i\cdot b^i.
\end{equation*}
Subsection 5.2.1 Integer representations
We typically use decimal (base \(10\)) notation to represent integers. For example,\(253\) means \(2 \cdot 10^2 + 5 \cdot 10^1 + 3 \cdot 10^0\text{.}\) The choice of base \(10\) is most likely due to the fact that we have \(10\) fingers.
There is no good mathematical reason to use base \(10\text{,}\) and in fact we can use any integer \(b \gt 1\) as a base.
Working with other bases is important. By abstracting to a general base \(b\text{,}\) we find that we understand the usual decimal operations better. Working in other bases also has applications.
For example, binary (base \(2\)) expansions are used to develop fast exponentiation techniques. This is a vital component of modern computer encryption schemes necessary for today’s digital world. Without secure means of communication, things such as online shopping would be impossible. In the next section we use base \(256\) for ASCII encoding, a character encoding standard for electronic communication.
Proof.
We prove the theorem by induction.
For \(n\in\NN\) let \(P(n)\) be “for \(a\lt b^n\) there are \(a_0,\dots,a_{n-1}\in\ZZ_b\) such that \(a=\sum_{i=0}^{n-1} a_i\cdot b^i\)”.
Let \(n=1\) and \(a\lt b^1=b\text{.}\) Then \(a\in\ZZ_b\text{.}\) Set \(a_0=a\text{.}\) Then \(\sum_{i=0}^{1-1} a_i\cdot b^i=a_0=a\text{.}\) Thus \(P(1)\) is true.
Fix \(k\in\NN\text{.}\) Suppose \(P(k)\) is true, that is “for \(a\lt b^k\) there are \(a_0,\dots,a_{k-1}\in\ZZ_b\) such that \(a=\sum_{i=0}^{k-1} a_i\cdot b^i\)”.
Let \(a\in\NN\) with \(a\lt b^{k+1}\text{.}\) By the division algorithm there are integers \(q\) and \(r\) with \(a=bq+r\) and \(0\le r\lt b\text{.}\) Then \(b^{k+1}\gt a=bq+r\ge bq\text{.}\) Division by \(b\) yields \(b^k\gt q\text{.}\)
By our induction hypothesis that \(P(k)\) is true, there are \(q_0,\dots,q_{k-1}\in\ZZ_b\) such that \(q=\sum_{i=0}^{k-1} q_i\cdot b^i\text{.}\) Thus
\begin{equation*}
a=bq+r=bq+r=b\left(\sum_{i=0}^{k-1} q_i\cdot b^i\right)+r=\sum_{i=1}^{k} q_{i-1}\cdot b^{i}+r.
\end{equation*}
Setting \(a_i=q_{i-1}\) and \(a_0=r\) we get
\begin{equation*}
a=\sum_{i=1}^{k} q_{i-1}\cdot b^{i}+r=\sum_{i=0}^{k} a_i\cdot b^i.
\end{equation*}
We have shown that \(P(1)\) is true and when \(P(k)\) is true then \(P(k+1)\) is true. Hence by the principle of mathematical inducion \(P(n)\) is true for all \(n\in\NN\text{.}\)
Definition 5.2.1.2.
The expression \({\sum_{i = 0}^k a_i b^i}\) of the theorem is known as a base \(b\) expansion, denoted \((a_ka_{k-1} \dots a_1 a_0)_b\)
Definition 5.2.1.3.
We call \(a={\sum_{i = 0}^k a_i b^i}\) in Theorem 5.2.1.1 the base \(b\) expansion of \(a\text{.}\) We also write \(a=(a_n,a_{n-1},\dots,a_2,a_1,a_0)_b\) and call this the base \(b\) representation of \(a\text{.}\) The parenthesis and commas in the base \(b\) representation are commonly omitted.
Example 5.2.1.4. Decimal representation.
We give numbers in base \(b\) and decimal (base 10) representation.
-
\(\displaystyle 10_2 = 1 \cdot 2^1 + 0 \cdot 2^0 = 2\)
-
\(\displaystyle 1001_2 = 1\cdot 2^3+0\cdot 2^2+ 0\cdot 2^1+1\cdot 2^0=8+1=9\)
-
\(\displaystyle 253_6 = 2\cdot 6^2+5\cdot 6^1+ 3\cdot 6^0=2\cdot 36+5\cdot 6+3\cdot 1=105\)
Example 5.2.1.5. Base \(b\) representation.
Let \(b\in\NN-\{1\}\text{.}\)
-
\(\displaystyle 0_b=0\)
-
\(\displaystyle 1_b=1\)
-
\(\displaystyle 10_b=b\)
-
\(\displaystyle 100_b=b^2\)
-
\(\displaystyle 1000_b=b^3\)
The positional values of a \(n\) digit base \(b\) number are
\begin{equation*}
b^{n-1},\,b^{n-2},\dots,\,b^2,\,b^1,\,b^0.
\end{equation*}
For base \(b\) with \(2\le b \le 36\) we use the first \(b\) characters from
\begin{equation*}
0\;1\;2\;3\;4\;5\;6\;7\;8\;9\;A\;B\;C\;D\;E\;F\;G\;\dots\;Z
\end{equation*}
for the base \(b\) digits in the base \(b\) representation, where the value of \(A\) is \(10\text{,}\) the value of \(B\) is 11 and so on.
Example 5.2.1.6. Hexadecimal expansion.
We give base 16 examples.
-
\(\displaystyle A_{16}=10\cdot 16^0=10\)
-
\(\displaystyle A0_{16}=10\cdot 16+0\cdot 16^0=160\)
-
\(\displaystyle A1_{16}=10\cdot 16+1\cdot 16^0=161\)
-
\(\displaystyle 1A_{16}=1\cdot 16+10\cdot 16^0=26\)
-
\(\displaystyle D_{16}=13\cdot 16^0=13\)
-
\(\displaystyle DADA_{16}=13\cdot 16^3+10\cdot 16^2+13\cdot 16^1+10\cdot 16^0=56026\)
-
\(\displaystyle FF_{16}=15\cdot 16^1+15\cdot 16^0=255\)
Example 5.2.1.7. Hexadecimal to decimal representation.
\begin{align*}
(1FAD)_{16} \amp = 1 \cdot 16^3 + F\cdot 16^2 + A \cdot 16^1 + D \cdot 16^0 \\
\amp = 1 \cdot 16^3 + 15\cdot 16^2 + 10 \cdot 16^1 + 13 \cdot 16^0 \\
\amp = 8109.
\end{align*}
How do we go the other way? Namely, given an integer \(n\) in decimal form and a positive base \(b\text{,}\) how can we compute the base \(b\)-expansion of \(n\text{?}\)
We can compute the base \(b\) expansion using div and mod. See the following examples. The first writes out the steps. The second is more condensed, given as a table.
Example 5.2.1.8. Decimal to binary representation.
Compute the binary (base \(2\)) expansion of \(67\text{.}\)
\begin{align*}
67 \amp = 33 \cdot 2+ \fbox{\(1\)} \\
33 \amp = 16 \cdot 2 + \fbox{\(1\)} \\
16 \amp = 8 \cdot 2 + \fbox{\(0\)} \\
8 \amp = 4 \cdot 2 + \fbox{\(0\)} \\
4 \amp = 2 \cdot 2 + \fbox{\(0\)} \\
2 \amp = 1 \cdot 2 + \fbox{\(0\)} \\
1 \amp = 0 \cdot 2 + \fbox{\(1\)}.
\end{align*}
The boxed terms give the base 2 expansion of \(67\) as
\begin{equation*}
67 = (1 0 0 0 0 1 1)_2.
\end{equation*}
In general, to convert \(a\in\NN\) to base \(b\) representation, we proceed as follows. Write:
\begin{align*}
a \amp =q_0\cdot b+r_0 \text{ where }r_0\in\ZZ_b \\
q_0 \amp =q_1\cdot b+r_1 \text{ where }r_1\in\ZZ_b \\
q_1 \amp =q_2\cdot b+r_2 \text{ where }r_2\in\ZZ_b \\
\amp \vdots \\
q_{n-3} \amp =q_{n-2}\cdot b+r_{n-2}\text{ where }r_{n-2}\in\ZZ_b \\
q_{n-2} \amp =q_{n-1}\cdot b+r_{n-1}\text{ where }r_{n-1}\in\ZZ_b. \\
\text{Until }q_{n-1} \amp =0
\end{align*}
Then \(a=\sum_{i=0}^{n-1} r_i\cdot b^i\text{,}\) that is,
\begin{equation*}
a= (((\dots(r_{n-1}\cdot b+r_{n-2})\cdot b+\dots r_2)\cdot b+r_1) \cdot b+r_0.
\end{equation*}
The function Listing 5.2.1.9 assumes that \(\mathtt{a}\in\NN\cup\{0\}\) and \(\mathtt{b}\in\NN-\{1\}\text{.}\)
def base_b_expansion(b,a):
"""
The list L of coefficients of the base b
expansion of a, such that b = L[0]+L[1]*b+L[2]+b^2+...
"""
L = [ ]
while a != 0:
q,r = divmod(a,b)
L.append(r)
a = q
return L
Example 5.2.1.10. Decimal to binary representation.
We find the base 2 representation \((r_{n-1}\dots r_1 r_0)_2\) of \(253\text{.}\)
\begin{align*}
253 \bmod 2 \amp= 1 \amp \mbox{ thus } r_0=1 \\
253 \div 2 \amp = 126 \\
126 \bmod 2 \amp = 0 \amp \mbox{ thus } r_1=0 \\
126 \div 2 \amp = 63 \\
63 \bmod 2 \amp = 1 \amp \mbox{ thus } r_2=1 \\
63 \div 2 \amp = 31 \\
31 \bmod 2 \amp = 1 \amp \mbox{ thus } r_3=1 \\
31 \div 2 \amp = 15 \\
15 \bmod 2 \amp = 1 \amp \mbox{ thus } r_4=1 \\
15 \div 2 \amp = 7 \\
7 \bmod 2 \amp = 1 \amp \mbox{ thus } r_5=1 \\
7 \div 2 \amp = 3 \\
3 \bmod 2 \amp = 1 \amp \mbox{ thus } r_6=1 \\
3 \div 2 \amp = 1 \\
1 \bmod 2 \amp = 1 \amp \mbox{ thus } r_7=1 \\
1 \div 2 \amp = 0
\end{align*}
Thus \(253=11111101_2\text{.}\)
Example 5.2.1.11. Decimal to hexadecimal.
We find the base 16 representation \((r_{n-1}\dots r_1 r_0)_{16}\) of \(253\text{.}\)
\begin{align*}
253 \bmod 16\amp = 13 \amp \mbox{ thus } r_0=13 \\
253 \div 16 \amp = 15 \amp \\
15 \bmod 16 \amp = 15 \amp \mbox{ thus } r_1=15 \\
15 \div 16 \amp = 0 \amp
\end{align*}
Thus \(253=15\cdot 16^1+13\cdot 16^0=FD_{16}\text{.}\)
The interactive tool in Figure 5.2.1.12 lets you explore how counting in other bases works.
2, 3, 4, …, to change the base. Click on +1, …, +10, … to increment both the representation of the number in the chosen base and base 10. Click on 0 to reset to \(0\text{.}\)
https://xkcd.com/953/) If you get an 11/100 on a CS test, but you claim it should be counted as a `C’, they’ll probably decide you deserve the upgrade.
