Positional numeral systems

Summary

This lesson studies positional notation, in which the value of each digit depends on the place it occupies. It proves that every natural number is written in exactly one way in any base $b \geq 2$ , by a procedure that consists in dividing repeatedly by the base, and teaches how to convert numbers between base $10$ and bases $2$ , $8$ and $16$ , and between the latter by grouping binary digits. It shows that addition and multiplication are carried out in any base by the same rules as in base $10$ , explains why the divisibility tests work and extends them to other bases, and closes with a note on the history of numeration and on the use of base $2$ in computers.

Learning objectives

Interpret positional notation and compute the value of a number written in any base.
Prove the existence and uniqueness of the representation in base $b$ , and obtain it by successive divisions.
Convert numbers between bases $2$ , $8$ , $10$ and $16$ , and add and multiply in base $2$ .
Justify the divisibility tests for $b - 1$ and for $b + 1$ in base $b$ , and apply them in base $10$ and in other bases.

Positional notation

When we write $2025$ we do not add up four digits: each one is multiplied by a power of $10$ that depends on its place. The first $2$ is worth two thousands; the second, two tens. The digit $0$ indicates that there are no hundreds and, by occupying its place, keeps the others in the places that belong to them.

2025 = 2 \cdot 10^3 + 0 \cdot 10^2 + 2 \cdot 10 + 5

This principle, called positional notation, does not depend on the number $10$ . If $b \geq 2$ is a natural number, called the base, the digits in base $b$ are the numbers $0, 1, \ldots, b - 1$ , and a sequence of digits $a_k, a_{k-1}, \ldots, a_1, a_0$ , with $a_k \neq 0$ , represents the number

n = a_k b^k + a_{k-1} b^{k-1} + \cdots + a_1 b + a_0

The digits are written side by side, from left to right, and the base is indicated as a subscript: for example, $3412_5$ is the number that in base $5$ is written with the digits $3$ , $4$ , $1$ and $2$ , and it is read “ $3412$ in base $5$ ”. The digit $a_i$ is said to occupy place $i$ , counted from the right starting at $0$ . Without a subscript, a number is written in base $10$ . In base $2$ there are only two digits, $0$ and $1$ , which are called bits; in base $16$ sixteen are needed, and the letters A, B, C, D, E and F, worth $10$ , $11$ , $12$ , $13$ , $14$ and $15$ , are added to the usual ten digits.

Now, the value of a number written in base $b$ can be computed by factoring out $b$ again and again, which avoids computing powers: this is Horner’s rule.

LemmaHorner’s rule

For every $k$ and all numbers $a_0, a_1, \ldots, a_k$ , the sum of the products $a_i b^i$ is obtained by starting from $a_k$ and repeating $k$ times the operation of multiplying by $b$ and adding the next coefficient.

a_k b^k + a_{k-1} b^{k-1} + \cdots + a_1 b + a_0 = (\cdots((a_k b + a_{k-1}) b + a_{k-2}) \cdots) b + a_0

The proof is an induction on $k$ that uses only distributivity. The expression is the value at $x = b$ of the polynomial $a_k x^k + \cdots + a_1 x + a_0$ , and the lesson on the algebra of polynomials will return to it.

Proof

$a_0 = a_0$
Base step: for $k = 0$ , both sides reduce to $a_0$ , because the rule performs no operation.
$\dato{h}{c_k b^k + \cdots + c_1 b + c_0 = (\cdots(c_k b + c_{k-1}) \cdots) b + c_0}$
Induction hypothesis: the rule holds for every sum of $k + 1$ terms, with arbitrary coefficients, that goes up to the power $b^k$ .
$a_{k+1} b^{k+1} + \cdots + a_1 b + a_0 = \resaltar{(a_{k+1} b^k + \cdots + a_2 b + a_1)} \, b + a_0$
Consider a sum that goes up to $b^{k+1}$ . By distributivity, $b$ is factored out of all the terms except the last.
$a_{k+1} b^{k+1} + \cdots + a_1 b + a_0 = \resaltar{((\cdots(a_{k+1} b + a_k) \cdots) b + a_1)} \, b + a_0$
The parenthesis has the form of the induction hypothesis, with the coefficients $c_i = a_{i+1}$ ; it is written with the rule, and multiplying it by $b$ and adding $a_0$ gives the rule for $k + 1$ . By the principle of induction, it holds for every $k$ .

ExampleThe value of a number written in base 5

Compute the number that in base $5$ is written $3412_5$ , in two ways: by adding the values of the places and with Horner’s rule.

Proof

$3412_5 = \resaltar{3} \cdot 5^3 + \resaltar{4} \cdot 5^2 + \resaltar{1} \cdot 5 + \resaltar{2}$
Each digit is multiplied by the power of $5$ that corresponds to its place: $5^3$ , $5^2$ , $5$ and $1$ .
$3 \cdot \resaltar{125} + 4 \cdot \resaltar{25} + 1 \cdot 5 + 2 = \resaltar{375} + \resaltar{100} + 5 + 2 = \dato{v}{482}$
We compute the powers and the products, and add.
$3412_5 = \resaltar{((3 \cdot 5 + 4) \cdot 5 + 1)} \cdot 5 + 2$
With Horner’s rule we factor $5$ out of the first three terms, and then out of the first two inside the parenthesis.
$\resaltar{3 \cdot 5 + 4} = 19, \quad \resaltar{19 \cdot 5 + 1} = 96, \quad \resaltar{96 \cdot 5 + 2} = \resaltar{482}$
The computation goes from the inside out: each result is multiplied by the base and the next digit is added to it. The same value is obtained, without any power.

In the rest of this lesson

Existence and uniqueness of the representation
Bases 2, 8 and 16
Operations in base 2
The divisibility tests
Divisors of the base
Divisibility by $b - 1$ and by $b + 1$
A historical and applied note
Solved problems
A number that is twice its reverse
The permuted digits
Palindromes with an even number of digits
Multiplying by doubling
Bachet’s weights
Proposed problems
The digits of a power without computing it
An internet address
From base 3 to base 9
Divisibility by 7, by 11 and by 13
Doubles in two bases