Natural numbers

Natural numbers are used to count indivisible objects e.g. fingers. Let’s take a look how we can handle them in the most effective way.

Natural numbers are: 1, 2, 3, 4, 5 etc. sometimes 0 is considered to be natural too. We all have an intuitive understanding of what a natural number is but is it possible to define it somehow?

Four apples are not the same as four lemons, yet four in both cases has the same meaning independent of apples, lemons or anything else.

Natural numbers can be defined as a category describing the quantity of objects. The category in question has the properties that are independent from the objects we count. Let’s explore them starting with the feature called order.

Order

If person A has ten apples and person B seven, person A has more apples than person B. Trivial!

It’s clear that any two numbers can only be either equal to each other or one of them must be greater. From this it follows that all natural numbers can be listed in the ascending or descending order.

Let’s use variables “a” and “b” to represent numbers. We will use the following symbols to denote the relationships discussed:

a>b        “a” is greater than “b”
a=b        “a” is equal to “b”
a<b        “a” is less than “b”

As we will see later, sometimes it is useful to combine “>” or ”<” with “=”. For this purpose, we will use the following symbols:

a≥b “a” is greater than or equal to “b”
a≤b “a” is less than or equal to “b”

Addition

I don’t think addition requires any introduction so let’s jump straight to studying its properties. We will do this using an example: baskets full of apples 😊.

It is obvious that it doesn’t matter in what order we add up individual baskets’ apple counts, the grand total of all the apples will always be the same. In other words, addition is order independent. Can we somehow express this in a more compact way?

Let’s start with just two baskets. The addition order independence is valid irrespective of quantity of apples, so instead of concrete numbers, we will use variables “a” and “b” to denote the number of apples in each basket. Once we do that, the case of two baskets is rather trivial:

Eq.1: a+b=b+a

How about three baskets?
a+b+c

First, we need to agree what the above statement means. Let’s adopt the rule of performing additions from left to right:

a+b+c=((a+b)+c)

where “a”, “b” and “c” are quantities of apples in each of three baskets.

With this in mind, the addition order independence for three baskets can be expressed as:

a+b+c=c+b+a
a+b+c=c+a+b
a+b+c=b+a+c
a+b+c=b+c+a
a+b+c=a+c+b

That’s five equalities, and for more baskets, it quickly gets out of hand. Can we replace them with fewer?

It turns out that if we adopt:

Eq.2: (a+b)+c=a+(b+c)

and eq.1, then we can reproduce all five equalities listed above.

Let’s prove, for example, that: a+b+c=c+b+a

a+b+c=(a+b)+c

which, thanks to eq.1, can be transformed into:
=c+(a+b)

After applying eq.1 to the part in red, we get:
=c+(b+a)

and finally, we can move the brackets using eq.2:
=(c+b)+a=c+b+a

All the five equalities can be proved in a similar way.

What happens if we add a fourth basket to the mix?
a+b+c+d

Just like before, eq.1 and 2 allow us to change the order of summation in any way we want.

For example, let’s move “d” to the beginning.

a+b+c+d=((a+b)+c)+d

First, we apply eq.1 to swap ((a+b)+c) with “d”:
=d+((a+b)+c)

After that we apply eq.2 twice:
=(d+(a+b))+c
=((d+a)+b)+c

and “d” becomes the first term:
=d+a+b+c

Thanks to eq.1 and 2, we can change the order of summation for five baskets, for six baskets and for more. In other words, we have proved that eq.1 and 2 imply that the result of addition is order independent.

Implication in the other direction gave us eq.1 and 2 in the first place so we have the equivalence:

“Addition is order independent” $\boldsymbol{\Leftrightarrow}$ a+b=b+a $\boldsymbol{\wedge}$ (a+b)+c=a+(b+c)

Eq.1: a+b=b+c is known in mathematics as the commutative property of addition, and eq.2: (a+b)+c=a+(b+c) as the associative property of addition. Of course, both of them hold irrespective of what we count.

Multiplication

The statement “a” apples can be also understood as: one apple taken “a” times. What happens if we replace apple with some number “b”?

To preserve the logic of the statement, the new one has to mean: baskets containing “b” objects each taken “a” times. We call this operation multiplication. To indicate that we mean to multiply, we insert “∙” between numbers “a” and “b”.

Now that we have a definition, let’s examine the properties. Multiplication is simply addition performed multiple times, so perhaps it has the same properties as addition.

Is multiplication commutative: a∙b=b∙a?

It is not as obvious as for addition. We will have to use a trick to see it clearly. The operation 3∙6 can be represented as a table with six columns and three rows. If we rotate it 90 degrees, we still have the same number of cells in the table, however this time it represents 6∙3:

Of course, we can do the same trick for any pair of natural numbers, so indeed multiplication is commutative:

Eq.3: a∙b=b∙a

Is multiplication associative: (a∙b)∙c=a∙(b∙c) ?

Let’s use the table trick again. In 3D a table turns into a cube. In the picture on the left we have “a” layers, “b” rows and “c” columns.

The number of cells in every layer is: b∙c and we have “a” of them, so the number of cells in the cube must be: a∙(b∙c).

Of course, we can rotate the cube and now we have: “c” layers, “a” rows and “b” columns (see the picture on the right). This time there are a∙b elements in every layer so after adding them up we have: c∙(a∙b) cells.

Rotation of the cube doesn’t change the number of cells so: a∙(b∙c)=c∙(a∙b). We already know that multiplication is commutative so we can rewrite it into:

Eq.4: (a∙b)∙c=a∙(b∙c)

and we have proved that multiplication is associative.

Can we multiply 4 elements in any order without changing the result?

Visualizing a four-dimensional cube is not possible but it doesn’t matter. We can use eq.3 and 4 to prove that we can multiply “n” numbers in any order and the result must always be the same. It can be done in exactly the same way as for addition in the previous section, we simply use eq.3 and 4 instead of 1 and 2.

Combination of addition and multiplication

Let’s start with a simple example:

6 apples = 2 apples + 4 apples

If A represents one apple, we can write the above as:

6∙A=(2∙A)+(4∙A)

Now, let’s replace A for example with the number 3 and use the visual representation of multiplication from the previous section:

It is clear that: 6∙3=(2+4)∙3=(2∙3)+(4∙3).

The same trick works for other numbers too, so the following equation must be true:

(a+b)∙c=(a∙c)+(b∙c)

Note that on the right-hand side we had to use brackets because it matters whether we multiply or add first:

(2∙3)+(4∙3)=18

2∙(3+4)∙3=42

To avoid the confusion and simplify the notation, we will assume: a+b∙c = a+(b∙c) that is: we always perform multiplications first! Of course, from this it follows that: a∙b+c∙d=(a∙b)+(c∙d) etc.

With that in mind we can write:

Eq.5: (a+b)∙c=a∙c+b∙c

The fact that the left side is always equal to the right, irrespective of numbers inserted, is called the distributive property of multiplication over addition.

Note that the property holds for three terms too:

(a+b+c)∙d=((a+b)+c)∙d=(a+b)∙d+c∙d=(a∙d+b∙d)+c∙d= a∙d+b∙d+c∙d

In the same fashion we can prove that:

$(a_1+a_2+\ldots+a_{n-1}+a_n)\cdot b=$
$a_1\cdot b+a_2\cdot b+\ldots+a_{n-1}\cdot b+a_n\cdot b$

To shorten the notation of summation for variables with consecutive indices: 1, 2, 3,…, n-1, n, we will use the symbol sigma: $\sum$ .

$\sum_{i=1}^{n}a_i:=a_1+a_2+\ldots+a_{n-1}+a_n$

The left side is defined as a shorthand for the right.

With this in mind we can write:

$(\sum_{i=1}^{n}a_i)\cdot b=(a_1+\ldots+a_n)\cdot b$
$=a_1\cdot b+\ldots+a_n\cdot b=\sum_{i=1}^{n}a_i\cdot b$

Now you may wonder: if distributive property of multiplication over addition holds, perhaps distributive property of addition over multiplication would work too:

(a∙b)+c=(a+c)∙(b+c) ?

Let’s try for example a=1, b=2 and c=3:

Left-hand side: (1∙2)+3=5 is not equal to the right-hand side: (1+3)∙(2+3)=20.

If (a∙b)+c=(a+c)∙(b+c) doesn’t hold for a single concrete example, then it can’t be true in general.

Zero

Zero represents nothing. Can something represent nothing? Would that make any sense?

Romans didn’t have a numeral representing zero. Babylonians, who had a sophisticated numbers system begging for introduction of zero, didn’t use it either! So, it isn’t as obvious as we like to believe.

Is zero important at all?

It’s easy to check that zero has the following properties:

a+0=0+a=a and 0∙a=a∙0=0

It is also easy to verify that its introduction doesn’t violate the properties of addition and multiplication described in the previous sections. Just insert a=0, then b=0 and finally c=0 in the equalities below to see for yourself:

a+b=b+a (a+b)+c=a+(b+c)

a∙b=b∙a (a∙b)∙c=a∙(b∙c)

(a+b)∙c=a∙c+b∙c

As far as addition and multiplication are concerned, zero behaves just like any other number. It will become apparent very soon how incredibly useful it is!!!

Subtraction

Let’s say we had 10 apples and 8 of them were taken away. We are left with 2. Trivial!

How about if we had 10 apples and 15 were taken away. Obviously, this is not possible!!!

Subtracting “b” from “a” makes sense (i.e. the result is a natural number) only when “a” is greater or equal to “b” (a≥b).

Of course, subtraction is not commutative: a-b≠b-a.

Order of additions and subtractions

Does it matter in what order we perform additions and subtractions?

Let’s take a look at an example to find out:

5+11+7-10-2-3=23-10-2-3=13-2-3=11-3=8

In the line above, we have performed the operations from left to right as the universally accepted convention prescribes.

What happens if we change the order:

5+11+7-10-2-3=(5-3)+(11-10)+(7-2)=2+1+5=8

5+11+7-10-2-3=(5-2)+(11-10)+(7-3)=3+1+4=8

The result is the same.

Irrespective of how we do it, at the end of the day we always subtract the same subtotal of 15 from 23:

5+11+7-10-2-3=(5+11+7)-(10+2+3)=23-15=8

so the order in which we perform these operations cannot matter.

Combination of subtraction and multiplication

When it comes to addition and subtraction, the order of operations doesn’t matter. However, this is not the case for multiplication. So, to simplify the notation we will perform multiplications prior to subtractions as indicated by the brackets:

a-b∙c=a-(b∙c)

a∙c-b∙c=(a∙c)-(b∙c)

etc.

With this in mind, let’s start with a concrete example:

7 apples – 5 apples = 2 apples

If we choose A to represent a single apple, then we can write:

7∙A-5∙A=(7-5)∙A

It is reasonable to expect that if we replace apple with a number, the equation should still hold.

Let’s insert for example A=3 and use a graphical representation of multiplication:

indeed:

7∙3-5∙3=(7-5)∙3=2∙3

In the same way we can demonstrate that the equation holds for any choice of natural numbers as long as a≥b:

Eq.6: (a-b)∙c=a∙c-b∙c

We cannot have a<b because then the statement makes no sense for natural numbers.

Division

Let’s assume we have ten identical watches and want to divide them evenly among three people. Everyone ends up with three and there is one left. We could chop it into three pieces but then it would be a watch-no-more.

Division of two natural numbers is denoted with a/b or a÷b. It seldom produces a natural result. We usually end up with a leftover called the remainder of division. In the example above the remainder is equal to 1=10-3∙3 which is usually expressed as:

10 mod 3 = 1

where “10 mod 3” is read ten modulo three.

Just like subtraction, division is not commutative: a/b ≠ b/a.

Preservation of equalities and inequalities

Let’s assume that two natural numbers “a” and “b” are equal to each other: a=b. If we add or subtract the same number c to/from both sides, of course the equality must still hold: a+c=b+c, a-c=b-c.

Let’s take a look at a few examples:

If a=b+c, then we can subtract “c” on both sides: a-c=b+c-c=b+(c-c)=b+0=b.

If a=d-e, then the following must be true as well: a+e=d-e+e=d+e-e=d+(e-e)=d.

It’s clear that multiplying both sides of a=b times “c” doesn’t affect the equality either: a∙c=b∙c.

What about inequalities?

If basket “b” contains more apples than basket “a”: a<b, then adding or subtracting the same number of apples to/from both baskets cannot change the relation “<” between the totals:

a+e<b+e and a-e<b-e

Obviously, the same property holds for ≤ as well:

$a \le b$ $\boldsymbol{\Rightarrow}$ $a \pm e \le b \pm e$

What happens if we multiply both sides of c<d times e?

If we have baskets containing “e” apples each, then obviously the total number of apples in “c” baskets will be smaller than the total in “d” baskets:

c∙e<d∙e

Note that this inequality is false for the empty basket e=0.

Relation ≤ on the other hand doesn’t have this problem:

$c \le d$ $\boldsymbol{\Rightarrow}$ $c \cdot e \le d \cdot e$

for any natural “c”, “d” and “e” including 0.

Representations of numbers

The decimal representation of numbers is usually taken for granted and hardly anybody pauses to contemplate how clever it is.

To appreciate fully what we’ve got, forget everything you know about numerals and imagine you have to start from scratch.

The first representation of numbers that springs to mind is:

I, II, III, IIII, IIIII, IIIIII etc.

That becomes impractical very quickly. The obvious solution is to use a different symbol for every number one can imagine. That would be compact, yet very impractical as well.

To address the problem, we could use some kind of mnemonic procedure for generating new symbols. In fact, that’s exactly what we do with words that represent numbers. For example: three, thirteen, thirty and the same pattern is used for other numbers.

Let’s simplify that by replacing words with symbols.

The Roman System

The Romans used a small set of simple symbols:

one:           I
five:          V
ten:           X
fifty:         L
hundred:       C
five hundred:  D
thousand:      M

To represent the consecutive numbers from one to nine, they were combining the symbols for one, five and ten in the following manner:

I, II, III, IV, V, VI, VII, VIII, IX.

Consecutive multiples of ten, i.e. ten, twenty, thirty etc., follow a similar pattern, however, this time we encounter the symbols for ten (X), fifty (L), and hundred (C):

X, XX, XXX, XL, L, LX, LXX, LXXX, XC.

Exactly the same principle is applied for multiples of hundred. In this case the symbols used represent hundred (C), five hundred (D), and thousand (M):

C, CC, CCC, CD, D, DC, DCC, DCCC, CM

More complicated numbers are put together in blocks. The first one contains multiples of thousand, the second: multiples of hundred, the third: multiples of ten, and finally a number between one and nine.

For example: thousand eight hundred and sixty nine.

Thousands: M
Hundreds:  DCCC = eight hundred
Tens:      LX   = sixty
Below ten: IX   = nine

Altogether: MDCCCLXIX

What is the maximal number we can express using this system?

MMM CM XC IX=three thousand, nine hundred, ninety and nine

To go past this point we would need to introduce a new symbol for five thousand. If we agreed to use for example W, then four thousand would be represented by MW.

The obvious flaw of this system is that we need new symbols for greater and greater numbers. Is it possible to represent every number imaginable using a limited set of symbols?

Expressing numbers with only two symbols

Is it possible to express numbers using only two symbols? Let’s see how far we can get with say: “a” and “b”. We can express only two numbers with that, however, we can go around this problem by using sequences. Altogether we can produce four different combinations with a sequence having two positions instead of just one:

aa, ba, ab, bb

After adding a third position, we have eight unique strings:

aaa, baa, aba, bba, aab, bab, abb, bbb

By adding more positions we can extend this system to infinity. What’s left to do is establishing the correspondence between sequences and numbers.

One way of doing that is demonstrated in the table below where C₀ represents the 0-th position in the string, C_I the first etc.

For example, the number ten has the following address in the table: a in the column C₀, b in C_I, a in C_II, b in C_III, a in C_IV. On the right hand side the table can be extended to infinity so we have:

Ten = ababaaaaaaaaaaaaaaaaa …

Starting with position C_IV the sequence representing the number ten consists of “a” only so we can cut it short at C_III:

Ten = abab

and simply remember that past this point there is “a” at every position of the sequence.

Note that every number in the table is represented by a unique sequence.

Number	C₀	C_I	C_II	C_III	C_IV	…
Zero	a	a	a	a	a	a
One	b	a	a	a	a	a
Two	a	b	a	a	a	a
Three	b	b	a	a	a	a
Four	a	a	b	a	a	a
Five	b	a	b	a	a	a
Six	a	b	b	a	a	a
Seven	b	b	b	a	a	a
Eight	a	a	a	b	a	a
Nine	b	a	a	b	a	a
Ten	a	b	a	b	a	a
Eleven	b	b	a	b	a	a
Twelve	a	a	b	b	a	a
Thirteen	b	a	b	b	a	a
Fourteen	a	b	b	b	a	a
Fifteen	b	b	b	b	a	a
Sixteen	a	a	a	a	b	a
…	…	…	…	…	…	a
Thirty One	b	b	b	b	b	a
…	…	…	…	…	…	…

Do “a” and “b” have any numerical meaning?

Can we somehow figure out what the result is of e.g. “abab + bbbab” without painstakingly finding these two numbers in the table, adding them somehow, and then reverting the whole process to get the sequence of “a” and “b” representing the sum?

Perhaps instead of “a” and “b” we should use symbols that have a numerical meaning to begin with.

Expressing numbers with symbols that have numerical meaning, part I

Let’s adopt six symbols: 0, 1, 2, 3, 4, 5 with a standard numerical meaning. But why six? Well, why not? Our goal here is to establish how to express numbers greater than the quantity of symbols in such a way that the sequence preserves numerical meaning. We could adopt as many symbols as we wish. Also, we could make up some weird symbols instead of the standard ones. It doesn’t really matter.

The easiest way to accomplish what we want is to add together what we have already:

5+1=six
5+2=seven
5+3=eight
5+4=nine
5+5=2∙5=ten

Past the number ten we continue in the same fashion:

2∙5+1, … 2∙5+4,  2∙5+5=3∙5

3∙5+1, … 3∙5+4,  3∙5+5=4∙5

and we continue like this until we get to 4∙5+5=5∙5 and past this point:

5∙5+1,     … 5∙5+1∙5

5∙5+1∙5+1, … 5∙5+2∙5

…

5∙5+4∙5+1, … 5∙5+4∙5+5=
              =5∙5+5∙5=2∙5∙5

etc.

Note that every number on the list above has the following structure:

d₂∙5∙5 + d₁∙5 + d₀

where variables d₀ , d₁ , d₂ represent any numeral between 0 and 4. Why not 5? If e.g. in d∙5 we insert d=5, we get 5∙5 and it is equal to 1∙5∙5, so “d” doesn’t have to go all the way up to 5.

The greatest number represented by this sequence is:

4∙5∙5 + 4∙5 + 4

Let’s see what happens after we add 1 to the formula above:

4∙5∙5 + (4∙5 + 5) = 4∙5∙5 + 5∙5 = 5∙5∙5

From this it follows that the numbers greater than that can be expressed as:

d₃∙5∙5∙5 + d₂∙5∙5 + d₁∙5 + d₀

and we can continue this game indefinitely:

d₀ + d₁∙5 + d₂∙5∙5 + d₃∙5∙5∙5 + d₄∙5∙5∙5∙5 + d₅∙5∙5∙5∙5∙5 + …

Multiplications are always performed first, and the order of summation can be changed in whichever way we want. In the statement above we started with d₀ because that way it is easier to express the fact that the series goes on to infinity.

With just six symbols we can get to as great a number as we wish, and our symbols have numerical meaning however, we now have the problem of having to use long sequences of 5s multiplied by itself many times. A shorthand would be handy.

Natural powers

Writing down a multiplication of some number x by itself is a pain when the sequence is long:

x ∙ x ∙ x ∙ x ∙ x ∙…∙ x

Let’s adopt the following shorthand to simplify the notation:

Eq.7: x ⁿ := “n instances of x multiplied by each other”

read: “n-th power of x“
or: “x to n-th power“
or simply: “x power n“.

In agreement with this definition we can write:

Eq.8: x ^a+b = x ^a ∙ x ^b

Thanks to the commutative property of multiplication we have:

x ^a+b = x ^a ∙ x ^b = x ^b ∙ x ^a

and from eq.8 it follows that this must be equal to:

= x ^b+a

In other words, if we adopt eq.7, as a consequence we get:

x ^a+b = x ^b+a

so we must have:

a + b = b + a

We know this is true, so our definition (eq.7) doesn’t lead to contradiction. If it did, we would be forced to ditch it.

In a similar way we can demonstrate that the associative property of multiplication leads to the following equality:

x ^(a+b)+c = (x ^a ∙ x ^b ) ∙ x^c
= x ^a ∙ (x ^b ∙ x ^c ) = x ^a+(b+c)

which is in agreement with the associative property of addition so everything fits nicely together.

There is one wrinkle left to iron out though. So far we have demonstrated that zero behaves just like any other number, so we would expect x ⁰ to be equal to something. What is the result of multiplying x zero times by itself? Is it zero?

If zero behaves just like other numbers then x ^a+b = x ^a ∙ x ^b should hold for “a” and/or “b” equal to 0 as well:

x ⁿ = x ⁿ⁺⁰ = x ⁿ ∙ x ⁰
= x ⁰ ∙ x ⁿ = x ⁰⁺ⁿ = x ⁿ

x ⁰ ∙ x ⁰ = x ⁰

These equations are true only when:

Eq.9: x ⁰ = 1

so we are going to accept that as a result of 0-th power.

If you have the impression that we invent things as we go, you are right. In mathematics every statement is a consequence of other true statements, or conventions and definitions adopted earlier. As long as we don’t introduce a contradiction, it is good mathematics 🙂

Now you can have a crazy idea: “I will invent some definitions and rules out of thin air and check what the consequences are.”

Hold on to your hat … this very idea is called mathematics 😮

Mathematics is an open ended game where each puzzle solved produces a handful of new ones, and we just follow the thread.

Expressing numbers with symbols that have numerical meaning, part II

In part I we have established that in a system with six numerals: 0,1,2,3,4,5, representing numbers between zero and five, every other number can be expressed as a sequence:

d₀ + d₁∙5 + d₂∙5∙5 + d₃∙5∙5∙5 + d₄∙5∙5∙5∙5 + d₅∙5∙5∙5∙5∙5 + …

where 0≤d_i≤4 for every subscript i. Let’s rewrite this using the symbol of summation $\sum$ and a shorthand for sequences “5 ∙…∙ 5” introduced in the previous section:

$d_0+d_1\cdot 5+\ldots+d_n \cdot 5^n =\sum_{i=0}^{n}d_i\cdot 5^{i}$

The formula obtained is shorter, yet still quite cumbersome. How about we shorten the notation further by introducing a convention according to which the sequence “d_nd_n-1…d₁d₀” will be treated as an equivalent of the sum:

$d_n d_{n-1}\ldots d_1 d_0:=\sum_{i=0}^{n}d_i\cdot 5^{i}$

Let’s take a look at what 10 represents in this convention. We have d₀=0, d₁=1 and d₂=d₃=d₄=…=0. “d”s with a subscript greater than 1 can be ignored because 0010=010=10 etc. On the other hand we can’t ignore d₀=0 because we wouldn’t be able to tell the difference between “1” and “10”. Let’s change the order of summation so it is easier to read:

10 := 1∙5¹ + 0∙5⁰ = 1∙5 + 0∙1 = 5 😮

0010 := 0∙5³ + 0∙5² + 1∙5¹ + 0∙5⁰ = 5

Ten equals five! Nonsense, I’m not reading this garbage any more!

Relax and take a deep breath. At the beginning of this section we have agreed that we have only six symbols representing numbers from zero to five. Other numbers are supposed to be represented by a sequence of these symbols. It is not a decimal system, so 10 can be anything we want. In the example described above, it is equal to five.

Thanks to this shocking ascertainment we can get rid of the symbol 5 altogether:

$d_n d_{n-1}\ldots d_1 d_0=\sum_{i=0}^{n}d_i\cdot 10^{i}$

Note that equal by definition “:=” was replaced with „=” because a definition cannot rely on itself.

The system just described is called quinary because we use five symbols: 0,1,2,3,4 (5 is represented by 10 so we don’t need it), and quinary is derived from the Latin word meaning five (latin words are used for historical reasons).

If you felt like the introduction of this system was somewhat obscure, perhaps the table below will be helpful to see what’s going on.

Every number is equal to the sum of addresses from its corresponding columns multiplied by 5ⁱ where “i” is each column’s subscript.

Let’s take a look at an example, say forty nine:

144 := 1∙5² + 4∙5¹ + 4∙5⁰ = “twenty five” + “twenty” + “four”

We have ignored columns with subscript i>2 because all of them contain 0 for number “144”.

Numbers	C _i>2	C ₂	C ₁	C ₀
Zero	0∙5ⁱ	0∙5²	0∙5¹	0∙5⁰
One	0∙5ⁱ	0∙5²	0∙5¹	1∙5⁰
Two	0∙5ⁱ	0∙5²	0∙5¹	2∙5⁰
Three	0∙5ⁱ	0∙5²	0∙5¹	3∙5⁰
Four	0∙5ⁱ	0∙5²	0∙5¹	4∙5⁰
Five	0∙5ⁱ	0∙5²	1∙5¹	0∙5⁰
Six	0∙5ⁱ	0∙5²	1∙5¹	1∙5⁰
Seven	0∙5ⁱ	0∙5²	1∙5¹	2∙5⁰
Eight	0∙5ⁱ	0∙5²	1∙5¹	3∙5⁰
Nine	0∙5ⁱ	0∙5²	1∙5¹	4∙5⁰
…	0∙5ⁱ	0∙5²	…	…
Twenty	0∙5ⁱ	0∙5²	4∙5¹	0∙5⁰
Twenty one	0∙5ⁱ	0∙5²	4∙5¹	1∙5⁰
Twenty two	0∙5ⁱ	0∙5²	4∙5¹	2∙5⁰
Twenty three	0∙5ⁱ	0∙5²	4∙5¹	3∙5⁰
Twenty four	0∙5ⁱ	0∙5²	4∙5¹	4∙5⁰
Twenty five	0∙5ⁱ	1∙5²	0∙5¹	0∙5⁰
…	0∙5ⁱ	1∙5²	…	…
Forty nine	0∙5ⁱ	1∙5²	4∙5¹	4∙5⁰
…	…	…	…	…

Note that if we replace 5 with 2, and use three symbols: 0,1,2, then our table turns into:

Number	C _i>II	C _II	C _I	C ₀
Zero	0∙2ⁱ	0∙2^II	0∙2^I	0∙2⁰
One	0∙2ⁱ	0∙2^II	0∙2^I	1∙2⁰
Two	0∙2ⁱ	0∙2^II	1∙2^I	0∙2⁰
Three	0∙2ⁱ	0∙2^II	1∙2^I	1∙2⁰
Four	0∙2ⁱ	1∙2^II	0∙2^I	0∙2⁰
Five	0∙2ⁱ	1∙2^II	0∙2^I	1∙2⁰
Six	0∙2ⁱ	1∙2^II	1∙2^I	0∙2⁰
Seven	0∙2ⁱ	1∙2^II	1∙2^I	1∙2⁰
…	…	…	…	…

Again, every number is equal to the sum of entries from the corresponding columns:

$d_n d_{n-1}\ldots d_1 d_0:=\sum_{i=0}^{n}d_i\cdot 2^{i}$

This time though:

10 := 1∙2 + 0 = 2

so we can get rid of the symbol 2 and use only: 0 and 1. The name of this system, binary, is derived from the Latin term “bini” meaning “a pair”.

Positional systems

Let’s apply the principle discovered in the previous section to a general case with an arbitrary number of symbols or rather digits as we will call them moving forward.

To start with, we have to agree on the symbols we will use. Consecutive numbers starting with zero will be represented by the following digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F etc. running up to some arbitrary number. Let’s agree to use a variable Γ’ (Gamma prime) as the greatest number represented by a single digit. Of course, Γ’ must be greater than zero.

If Γ’ is the greatest available digit, then the quantity of all the symbols must be Γ’+1 because we also have 0 representing nothing. For example, if Γ’=1, we have two digits available: 0 and 1. The quantity of all digits we decide to use will be called the base of the system and represented by a variable Gamma Γ=Γ’+1.

How can we express numbers greater than Γ ?

After we multiply all the available digits times Γ, we get a sequence:

0∙Γ,  1∙Γ,  2∙Γ,  3∙Γ 
   etc. up to (Γ-1)∙Γ

We went well above Γ, however there are gaps in the sequence. It doesn’t cover the consecutive numbers because Γ>1. The width of every gap is Γ, so we can fill these holes up with loose digits. After all they run from 0 to Γ’=Γ-1.

If we do that, then every consecutive number in our sequence can be coded as:

d₀ + d₁∙Γ

where d₀ and d₁ represent digits.

The greatest number we can get using this formula is:

(Γ – 1) + (Γ – 1)∙Γ = Γ – 1 + Γ² – Γ = (Γ – Γ) + Γ² – 1 = Γ² – 1

What about numbers greater than that?

Let’s multiply all digits available times Γ²:

0,  1∙Γ²,  2∙Γ²,  3∙Γ²
       ... ,  (Γ-1)∙Γ²

and again, we have gaps in the sequence. This time the width of every gap is Γ², so they can be filled up tightly with d₀ + d₁∙Γ which happens to cover all the numbers between 0 and Γ²-1.

A new formula d₀ + d₁∙Γ + d₁∙Γ² will produce every number up to:

(Γ – 1) + (Γ – 1)∙Γ + (Γ – 1)∙Γ² = Γ – 1 + Γ² – Γ + Γ³ – Γ² = Γ³ – 1

Continuation of this process leads to a general formula:

$\sum_{i=0}^{n}d_i\cdot \Gamma^{i}$

where d_i represent digits: 0 ≤ d_i ≤ Γ – 1.

After adopting the notation introduced in the previous section, we can rewrite the formula above into:

Eq.10: $d_n d_{n-1}\ldots d_1 d_0:=\sum_{i=0}^{n}d_i\cdot \Gamma^{i}$

Note that we don’t need a separate symbol for the base Γ, because we can code it with the available digits:

10 := 1∙Γ + 0 = Γ

so eventually we have:

Eq.11: $d_n d_{n-1}\ldots d_1 d_0=\sum_{i=0}^{n}d_i\cdot 10^{i}$

Directly from this formula we find:
1=10 ^zero,
10=10 ^one,
100=10 ^two,
1000=10 ^three,
10000=10 ^four
etc.

so we can rewrite eq.11 as:

Eq.12: $d_n d_{n-1}\ldots d_1 d_0=d_0 \cdot 1 + d_1\cdot 10 +$
$+ d_2 \cdot 100 + d_3 \cdot 1000 + \ldots$

It is important to remember that the numerical meaning of coding depends on the base Γ:

Binary system: Γ=10:=two, 100:=four, 1000:=eight, 10000:=sixteen, 100000:=thirty two etc.

Quinary system: Γ=10:=five, 100:=twenty five, 1000:=hundred and twenty five etc.

Decimal system: Γ=10:=ten, 100:=hundred, 1000:=thousand etc.

Hexadecimal system: Γ=10:=sixteen, 100:=two hundred and fifty six etc.

Quinary 44 = 4∙five + 4 = twenty four

Decimal 44 = 4∙ten + 4 = forty four

Hexadecimal 44 = 4∙sixteen + 4 = sixty eight

At this point you may wonder why decimal 123 is hundred and twenty three and not three hundred and twenty one. It kind of feels natural to start with the smaller numeral and move up.

The decimal system was borrowed from the Arabs who write from right to left. Perhaps nobody bothered to make the numerical system consistent with the western direction of writing 😀

The most common positional systems are decimal used in everyday life and binary used by computers.

The reason why I’m talking about exotic systems is to demonstrate how a positional system works without any preconceptions getting in the way. The principle behind them all is the same.

Now you may wonder why not use just one system, for example decimal. Why do computers utilize the binary system instead?

It will become apparent after we take a look at performing mathematical operations.

In the section where numbers were coded with “a” and “b” we were wondering if it is possible to add them directly in the form they are in. To be able to do that, we have introduced a system where numbers are expressed as a sum of digits multiplied by powers. Intuition suggests that in this form, addition should be easy. Let’s take a closer look.

Addition procedure

We will kick off this section with two concrete examples, the first in the binary and the second in the quinary system. The goal will be to figure out how to go about addition. Once we find a way, we will lay out the procedure using variables to make it general i.e. applicable to any numbers encoded in any system.

Example 1

Let’s add binary 1010 and 10111. The base (Γ) is equal to two, that is 10 in the binary system and the only available digits are: 0, 1. Also, please remember that all numbers in this example are expressed in the binary not a decimal system!

Thanks to eq.12:

$d_n d_{n-1}\ldots d_1 d_0=d_n \cdot 10^n + d_{n-1} \cdot 10^{n-1} +$
$+ \ldots + d_1\cdot 10 + d_0 \cdot 1$

we can rewrite 1010 and 10111 as:

1010=1000+10

10111=10000+100+10+1

10111+1010=10000+1000+100+10+10+1

10 represents two, 10+10=(1+1)∙10 is equal to four, and from the previous section we know that in the binary system four is represented by 100 thus:

10+10=100

After inserting this result into the formula for the sum 10111+1010, we get:

10111+1010=10000+1000+100+100+1

100 is four thus 100+100=(1+1)∙100 is eight represented in the binary system by 1000 (see the previous section):

100+100=1000

10111+1010=10000+1000+1000+1

1000 is eight, 1000+1000=(1+1)∙1000 is sixteen represented in the binary system by 10000:

1000+1000=10000

thus

10111+1010=10000+10000+1

Finally, sixteen plus sixteen is 10000+10000=(1+1)∙10000 that is thirty two represented by 100000 in the binary system. So:

10111+1010=100000+1=100001

It is quite apparent that the only relation one needs to know to perform addition in the binary system is:

10ⁿ+10ⁿ=(1+1)∙10ⁿ=10∙10ⁿ=10ⁿ⁺¹

Its equivalent in the decimal system reads:

2ⁿ+2ⁿ=(1+1)∙2ⁿ=2∙2ⁿ=2ⁿ⁺¹

In closing, let’s convert 10111, 1010 and 100001 to a decimal system to verify the result in the notation imprinted upon our brains. For this purpose we will use eq.10:

$d_n d_{n-1}\ldots d_1 d_0:=\sum_{i=0}^{n}d_i\cdot \Gamma^{i}$

where the right-hand side i.e. Γ and powers “i”, will be expressed in the decimal system:

Binary 1010 is decimal: 1∙2³ + 1∙2¹=8+2=10

Binary 10111 is decimal: 1∙2⁴ + 1∙2² + 1∙2¹ + 1∙2⁰=16+4+2+1=23

Binary 100001 is decimal: 1∙2⁵ + 1∙2⁰=32+1=33

As expected, the results obtained in both systems are the same.

Example 2

Let’s add 323 and 314. This time, all numbers will be expressed in the quinary system so Γ=five=10 and the only available digits are: 0, 1, 2, 3, 4.

323=3∙100+2∙10+3∙1

314=3∙100+1∙10+4∙1

323+314=(3+3)∙100+(2+1)∙10+(3+4)∙1

3+4=seven=1∙five+2=1∙10+2

323+314=(3+3)∙100+(2+1)∙10+1∙10+2

and

323+314=(3+3)∙100+4∙10+2

3+3=six=1∙five+1=11

thus

(3+3)∙100=11∙100

323+314=11∙100+4∙10+2=1142

Just like before we will verify the result in our decimal darling. We will use eq.10:

$d_n d_{n-1}\ldots d_1 d_0:=\sum_{i=0}^{n}d_i\cdot \Gamma^{i}$

where Γ and powers on the right are expressed in a decimal system.

Quinary 323 is decimal: 3∙5² + 2∙5¹ + 3∙5⁰ = 75 + 10 + 3 = 88

Quinary 314 is decimal: 3∙5² + 1∙5¹ + 4∙5⁰ = 75 + 5 + 4 = 84

Quinary 1142 is decimal: 1∙5³ + 1∙5² + 4∙5¹ + 2∙5⁰ = 125 + 25 + 20 + 2 = 172

In the decimal system we have 88+84=172, so all is good.

The addition procedure for every positional system is the same and can be described using variables. Let’s add some arbitrary two numbers: N₁ and N₂ expressed in a positional system with the base Γ:

$N_1=\sum_{i=0}^{n}d_{1,i}\cdot \Gamma^{i}$

$N_2=\sum_{i=0}^{m}d_{2,i}\cdot \Gamma^{i}$

The first variable in the subscript of a digit d_q,i indicates whether this digit belongs to N₁ or N₂, and the second variable (“i”) corresponds to the position of a digit in a sequence representing the number in question.

To perform the summation, first, we group the digits multiplied by the same power:

$N_1+N_2=\sum_{i=0}^{k}(d_{1,i}+d_{2,i})\cdot \Gamma^{i}$

where variable k is equal to whichever is greater: n or m.

We know that the result of d_1,i + d_2,i can overflow (it may not be possible to express it with a single digit) so we will start the summation from the lowest power i=0: d_1,0 + d_2,0.

The question is how much d_1,0 + d_2,0 can spill over beyond Γ’ i.e. the greatest number represented by a single digit in our system. The upper limit of d_1,0 + d_2,0 is Γ’+Γ’ and Γ’=Γ-1. So:

d_1,0 + d_2,0 ≤ Γ’+Γ'<Γ+Γ

If that’s the case, then d_1,0 + d_2,0 can spill over into one position higher and not any further.

In other words, the result of d_1,0 + d_2,0 can be expressed using only two digits. We will use variables l₀ and h₀ to denote them:

$d_{1,0}+d_{2,0} = l_0 + h_0 \cdot \Gamma<\Gamma+\Gamma$

Of course if there is no overflow, then h₀=0, otherwise h₀=1.

Let’s insert this result into the sum N₁ + N₂. To be able to do that, we will write the first two terms of N₁ + N₂ outside of the summation shorthand:

$N_1+N_2=(d_{1,0}+d_{2,0})\cdot \Gamma^0+$

$+(d_{1,1}+d_{2,1})\cdot \Gamma^1+$

$+\sum_{i=2}^{k}(d_{1,i}+d_{2,i})\cdot \Gamma^{i}$

and then insert d_1,0 + d_2,0= l₀ + h₀∙Γ in place of the first term:

$N_1+N_2=$

$=l_0 \cdot \Gamma^0+(h_0+d_{1,1}+d_{2,1}) \cdot \Gamma^1+$

$+\sum_{i=2}^{k}(d_{1,i}+d_{2,i})\cdot \Gamma^{i}$

Next, let’s deal with a term multiplied by Γ¹ i.e. h₀ + d_1,1 + d_2,1. We have to decide what to do with a potential overflow:

$h_0+d_{1,1}+d_{2,1}\le\Gamma'+\Gamma'+\Gamma'$

It is clear that it must be smaller than Γ² because Γ'<Γ’² for 1<Γ’:

$h_0+d_{1,1}+d_{2,1}\le\Gamma'+\Gamma'+\Gamma'<$

$<\Gamma'^2+\Gamma'+\Gamma'+1=(\Gamma'+1)^2=\Gamma^2$

and from the above it follows (see the earlier section) that we can find such digits l₁ and h₁ that:

$h_0+d_{1,1}+d_{2,1}=l_1+h_1\cdot\Gamma<\Gamma^2$

Let’s insert this result into the sum N₁ + N₂ as well:

$N_1+N_2=l_0 \cdot \Gamma^0+(h_0+d_{1,1}+d_{2,1}) \cdot \Gamma^1+$

$+(d_{1,2}+d_{2,2})\cdot \Gamma^2+\sum_{i=3}^{k}(d_{1,i}+d_{2,i})\cdot \Gamma^{i}=$

$=l_0\cdot \Gamma^0+l_1\cdot \Gamma^1 + (h_1+d_{1,2}+d_{2,2})\cdot \Gamma^2+$

$+\sum_{i=3}^{k}(d_{1,i}+d_{2,i})\cdot \Gamma^{i}$

Next, we can express the sum of three digits h₁ + d_1,2 + d_2,2 (the ones multiplied by Γ²) in terms of some digits l₂ and h₂:

$h_1+d_{1,2}+d_{2,2}=l_2+h_2\cdot\Gamma<\Gamma^2$

and insert this into N₁ + N₂ as well:

$N_1+N_2=l_0\cdot \Gamma^0+l_1\cdot \Gamma^1 +l_2\cdot \Gamma^2+$

$+(h_2+d_{1,3}+d_{2,3})\cdot\Gamma^3+$

$+\sum_{i=4}^{k}(d_{1,i}+d_{2,i})\cdot \Gamma^{i}$

Note that as we perform the summation for greater and greater “i”, we always encounter the following term:

$h_{i-1}+d_{1,i}+d_{2,i}$

that is a sum of three digits thus just like before we can find such digits l_i and h_i that:

$h_{i-1}+d_{1,i}+d_{2,i}=l_i+h_i \cdot \Gamma$

After inserting this term into N₁ + N₂, we move up to “i+1”. Eventually we are going to get to the highest power i=k and after inserting the last term, the final result reads:

$N_1+N_2=\sum_{i=0}^{k}l_i\cdot\Gamma^i+h_k\cdot\Gamma^{k+1}$

To add any two natural numbers, you just have to insert them in place of N₁ and N₂ and follow the procedure laid out. As long as you can find a representation of the sum of three digits (the ones at position “i” for N₁ and N₂ and a spill over from the previous step) in the following form:

$h_{i-1}+d_{1,i}+d_{2,i}=l_i+h_i \cdot \Gamma$

the rest of the addition procedure is entirely mechanical. You simply start the summation with digits multiplied by Γ⁰. The result of that may spill over into Γ¹, which in turn can spill over to Γ² etc.

Comparison procedure

It is possible to subtract natural N₁ from natural N₂ only when N₂≥N₁. The question is: how to figure out which number is greater when both are coded in some positional system?

Certainly if every digit of N₂ is greater, then N₂ must be greater. That would happen if every digit of N₂ was Γ-1 i.e. the greatest available:

$\sum_{i=0}^{n}d_{i}\cdot \Gamma^{i}\le\sum_{i=0}^{n}(\Gamma-1)\cdot \Gamma^{i}$

Let’s take a closer look at the sum on the right:

$\sum_{i=0}^{n}(\Gamma-1)\cdot \Gamma^{i}=\sum_{i=0}^{n}(\Gamma^{i+1}-\Gamma^i)=$

$=(\Gamma^1-\Gamma^0)+(\Gamma^2-\Gamma^1)+(\Gamma^3-\Gamma^2)+$

$+\ldots+(\Gamma^n-\Gamma^{n-1})+(\Gamma^{n+1}-\Gamma^n)=$

$=\Gamma^{n+1}-\Gamma^0<\Gamma^{n+1}$

Altogether we can write:

$\sum_{i=0}^{n}d_{i}\cdot \Gamma^{i}<\Gamma^{n+1}$

In every positional system 10 always represents Γ, the base of the system used (10:=Γ), so we can rewrite the formula above into:

$\sum_{i=0}^{n}d_{i}\cdot 10^{i}<10^{n+1}$

and use it to determine which out of two arbitrary numbers is greater.

Example 1

Which one is greater 100 or 11 and why?

Using the last inequality we can easily determine that:

11=1∙10+1∙1<10²=100

Example 2

Which is greater: 323 or 244?

Using the same inequality we conclude:

44=4∙10+4∙1<10²=100

After adding 200 on both sides, we get:

244<300

244<323

Example 3

Which is greater 777521 or 776888?

777521=770000+7521

776888=770000+6888

so all we have to do is to find out whether 7521 or 6888 is greater.

888=8∙100+8∙10+8∙1<10³=1000

After adding 6000 on both sides, the inequality reads:

6888<7000

6888<7521

The reasoning described above boils down to comparison of digits on the same position “i” starting from the left. For example:

100 and 011 – the leftmost digits are 1 and 0 respectively. 1>0 so 100>011

777521 and 776888 have digit 7 on the leftmost, fifth position (0-th position is the rightmost one). Digits on the fourth position are the same too, yet the ones on the third position are 7 and 6. 7>6, so 777521>776888.

Note that this procedure works irrespective of which positional system we use.

Subtraction procedure

We can tell which of two numbers is greater, so we know whether the operation of subtraction makes sense for natural numbers, where the result can’t be less than 0. Let’s try to find the subtraction procedure.

Example 1

Binary 1000-11=?

We will start with subtracting the digit multiplied by the lowest power Γ⁰:

1000-11=(1000-1)-10

The 0-th digit of 1000 is 0. We can’t perform 0-1 but 1000>1 so the subtraction must be possible:

1000=10∙100=(1+1)∙100=100+100=
=100+10∙10=100+(1+1)∙10=
=100+10+10=100+10+1+1

After that the subtraction becomes easy:

1000-11=100+10+1+1–1–10=
=100+1=101

Let’s verify the result in the decimal system:

Binary 1000 is decimal 8

Binary 10+1 is decimal 2+1=3

Binary 101 is decimal 4+1=5

and in the decimal system: 8-3=5

Example 2

Quinary 1023-42=?

1023=1000+2∙10+3

42=4∙10+2

1023-42=1000+(2-4)∙10+(3-2)=1000+(2-4)∙10+1

We can’t perform 2-4, but we can borrow some digits from 1000:

1000=10∙100=(4+1)∙100=4∙100+100=4∙100+10∙10=4∙100+(4+1)∙10

With that in mind, we get:

1023-42=4∙100+(4+1)∙10+(2-4)∙10+1=4∙100+(4+1+2-4)∙10+1=4∙100+3∙10+1=431

Let’s verify the result:

Quinary 1000+2∙10+3 is decimal 5³+2∙5+3=125+10+3=138

Quinary 4∙10+2 is decimal 4∙5+2=22

Quinary 431 is decimal 4∙5²+3∙5+1=100+15+1=116

and 138-22=116 in the decimal system.

The subtraction procedure is similar to the one used for addition. We start with subtracting digits which are on the same position. The difference is that for additions we had overflows, and for subtraction we have underflows.

Let’s describe the procedure using the variables from the section on addition:

$N_1=\sum_{i=0}^{n}d_{1,i}\cdot \Gamma^{i}$

$N_2=\sum_{i=0}^{m}d_{2,i}\cdot \Gamma^{i}$

We assume that N₂≥N₁ so m≥n.

The subtraction can be expressed as:

$N_2-N_1=\sum_{i=0}^{m}(d_{2,i}-d_{1,i})\cdot \Gamma^{i}$

We perform subtraction of digits starting with the lowest position i=0. As long as d_2,i – d_1,i ≥ 0, the result of subtraction produces a digit. If the result is below 0, we have to borrow from the term at the position “i+1”:

$(d_{2,i+1}-d_{1,i+1})\cdot\Gamma^{i+1}+(d_{2,i}-d_{1,i})\cdot\Gamma^{i}=$

$=(d_{2,i+1}-d_{1,i+1}-1)\cdot\Gamma^{i+1}+\Gamma^{i+1}+$

$+(d_{2,i}-d_{1,i})\cdot\Gamma^{i}=$

$=(d_{2,i+1}-d_{1,i+1}-1)\cdot\Gamma^{i+1}+$

$+\Gamma\cdot\Gamma^i+(d_{2,i}-d_{1,i})\cdot\Gamma^{i}=$

$=(d_{2,i+1}-d_{1,i+1}-1)\cdot\Gamma^{i+1}+$

$+(\Gamma+d_{2,i}-d_{1,i})\cdot\Gamma^{i}$

If d_2,i – d_1,i<0, then Γ + d_2,i – d_1,i is a digit, that is 0 ≤ Γ + d_2,i – d_1,i < Γ.

Now d_2,i+1 – d_1,i+1 – 1 may be negative and if it is, we borrow from “i+2” etc.

The procedure described is entirely mechanical. You can insert any two natural numbers in place of N₂ and N₁. As long as N₂≥N₁, the process boils down to performing subtractions of digits at every position “i”:

d_2,i – d_1,i for d_2,i ≥ d_1,i

Γ + d_2,i – d_1,i for d_2,i < d_1,i, where Γ was borrowed from the position i+1.

You start at i=0 and go all the way up to “m”, the greatest power for N₂.

Multiplication of natural numbers times 10 to the power of n

For numbers having the form 10ⁿ we can write 10^a+b=10^a∙10^b (n=a+b) so perhaps multiplying any number times 10ⁿ is easy in positional systems. Let’s take a look at an example:

123∙1000=(1∙10²+2∙10+3∙1)∙10³=1∙10⁵+2∙10⁴+3∙10³=123000

Indeed, it is straightforward. It boils down to adding three zeros to the right of 123.

Does multiplying some arbitrary number times 10ⁿ is always equivalent to adding n zeros at the end of its positional representation?

$(\sum_{i=0}^{m} d_i\cdot 10^i)\cdot 10^n=\sum_{i=0}^{m}d_i\cdot 10^{i+n}$

After the multiplication, digit d₀ is multiplied by 10ⁿ, so it is not 0-th digit anymore. It is the n-th digit now. The powers lower than n are absent in the sum. In other words, digits at the positions from 0 to “n-1” must be all equal to 0.

Multiplication procedure

As usual, it will be easier to see how to multiply using a few concrete examples, before going full abstract to demonstrate it always works this way.

EXAMPLE 1

Binary (that is base Γ:=two) 101∙11=?

101∙(10+1)=101∙10+101∙1=1010+101=1111

EXAMPLE 2

Quinary (base Γ:=five) 123∙313=?

123∙313=123∙(3∙100+1∙10+3)=(123∙3)∙100+123∙10+123∙3

Let’s tackle 123∙3:

123∙3=(100+2∙10+3)∙3=3∙100+(2∙3)∙10+(3∙3)

3∙3=nine=1∙five+4=14=10+4 so:

123∙3=3∙100+(2∙3)∙10+(10+4)=3∙100+(2∙3+1)∙10+4

2∙3+1=seven=1∙five+2=12=10+2 thus:

123∙3=3∙100+(10+2)∙10+4=3∙100+100+2∙10+4=
=4∙100+2∙10+4=424

After inserting this result into 123∙313 we get:

123∙313=424∙100+123∙10+424=
=42400+1230+424

and we have a summation that we already know how to handle.

Next, let’s demonstrate how to multiply any two arbitrary natural numbers expressed in the positional system:

$N_1=\sum_{i=0}^{n}d_{1,i}\cdot \Gamma^{i}$

$N_2=\sum_{j=0}^{m}d_{2,j}\cdot \Gamma^{j}$

The multiplication reads:

$N_1 \cdot N_2=(\sum_{i=0}^{n}d_{1,i}\cdot \Gamma^{i}) \cdot (\sum_{j=0}^{m}d_{2,j}\cdot \Gamma^{j})$

Our goal is to transform this in such a way, that the result will have the following form:

$N_1 \cdot N_2=\sum_{j=0}^{J}x_j\cdot \Gamma^{j}$

where x_j are digits to be found and J is the greatest required power.

Let’s use the distributive property of multiplication over addition to convert the former equation into the latter. It can be done for example like this:

$N_1 \cdot N_2=(\sum_{i=0}^{n}d_{1,i}\cdot \Gamma^{i}) \cdot (\sum_{j=0}^{m}d_{2,j}\cdot \Gamma^{j})=$

$=\sum_{j=0}^{m}(\sum_{i=0}^{n}d_{1,i}\cdot\Gamma^i) \cdot (d_{2,j} \cdot \Gamma^{j})=$

$=\sum_{j=0}^{m}(\sum_{i=0}^{n}d_{1,i}\cdot d_{2,j} \cdot \Gamma^{i})\cdot \Gamma^{j}$

Index “i” is entirely contained within the brackets, so we can denote the sum over “i” with the variable X_j that is independent of “i”:

$X_j=\sum_{i=0}^{n}d_{1,i}\cdot d_{2,j} \cdot \Gamma^{i}$

and we almost have what we want:

$N_1 \cdot N_2=\sum_{j=0}^{m}X_j\cdot \Gamma^{j}$

albeit X_j are usually greater than digits (that is why I have used capital X instead of x).

Note that if we transformed the variables X_j (j=0,1,2,…,m) into the following form:

$X_j=\sum_{i=0}^{n}x_{j,i} \cdot \Gamma^{i}$

where x_j,i are digits, then we would be done because we already know how to handle multiplications X_j∙Γ^j and additions for numbers expressed in the positional system that is: as sums of digits multiplied by powers of the base Γ.

The problem is that X_j:

$X_j=\sum_{i=0}^{n}(d_{1,i}\cdot d_{2,j}) \cdot \Gamma^{i}$

does not have the form laid out in the previous paragraph. In other words, we cannot write:

$x_{j,i}=d_{1,i}\cdot d_{2,j}$

because the result of d_1,i∙d_2,j can be greater than the greatest available digit: Γ-1 and every x_j,i must be a digit.

To deal with this problem, first, we will grab the term for i=0: d_1,0 ∙ d_2,j in the sum constituting X_j and we will decompose d_1,0 ∙ d_2,j into a digit and a leftover in a similar way we did in the section about addition. Both d_1,0 and d_2,j are digits so d_1,0 ∙ d_2,j must be in the range:

$0 \le d_{1,0}\cdot d_{2,j} \le (\Gamma-1)\cdot(\Gamma-1)<\Gamma^2$

because Γ-1 is the greatest available digit. As we know, every number in this range can be expressed as:

$d_{1,0}\cdot d_{2,j}$ $=$ $s_{j,0}$ $+$ $h_{j,0}$ $\cdot\Gamma$

where s_j,0 and h_j,0 are both some digits (h_j,0 ∙ Γ is the overflow). The first index “j” tells us which X_j the digits belong to and the second, which term in the sum we are handling. i=0 is the very first term.

Next, let’s put the first two terms of X_j outside of the summation shorthand and then replace the first term with its equivalent found above:

$X_j=$ $d_{1,0}\cdot d_{2,j}$ $+ d_{1,1}\cdot d_{2,j}\cdot\Gamma+\sum_{i=2}^{n}d_{1,i}\cdot d_{2,j} \cdot \Gamma^{i}=$

$=$ $s_{j,0}$ $+($ $h_{j,0}$ $+d_{1,1}\cdot d_{2,j})\cdot\Gamma+\sum_{i=2}^{n}d_{1,i}\cdot d_{2,j} \cdot \Gamma^{i}$

Now we have an overflow in the term in the brackets: h_j,0+d_1,1∙d_2,j. It constitutes a number in the range:

$0 \le h_{j,0}+d_{1,1}\cdot d_{2,j} \le (\Gamma-1)+(\Gamma-1)\cdot(\Gamma-1)=$

$=(\Gamma-1)\cdot(1+(\Gamma-1))<\Gamma^2$

so just like before, there must exist digits s_j,1 and h_j,1 such that:

$h_{j,0}+d_{1,1}\cdot d_{2,j}$ $=s_{j,1}+h_{j,1}\cdot\Gamma$

After inserting this into the formula for X_j:

$X_j=s_{j,0}+($ $h_{j,0}+d_{1,1}\cdot d_{2,j}$ $)\cdot\Gamma+(h_{j,1}+d_{1,2}\cdot d_{2,j})\cdot\Gamma^2+$

$+\sum_{i=3}^{n}d_{1,i}\cdot d_{2,j} \cdot \Gamma^{i}$

we get:

$X_j=s_{j,0}+s_{j,1}\cdot\Gamma+($ $h_{j,1}+d_{1,2}\cdot d_{2,j}$ $)\cdot\Gamma^2+\sum_{i=3}^{n}d_{1,i}\cdot d_{2,j} \cdot \Gamma^{i}$

and the next term with a potential overflow is the one multiplied by Γ².

The terms with an overflow we have seen so far were: h_j,0+d_1,1∙d_2,j for the index i=1 and h_j,1+d_1,2∙d_2,j for i=2. Note that as we move towards higher indices “i”, the term with a potential overflow always has the form:

$h_{j,i-1}+d_{1,i}\cdot d_{2,j}$

where h_j_,_i-1 is the overflow from the previous step: i-1. We have already proved that it must stay between 0 and Γ²-1, thus we can always find digits s_j,i and h_j,i such that:

$h_{j,i-1}+d_{1,i}\cdot d_{2,j}=s_{j,i}+h_{j,i}\cdot\Gamma$

After transforming every term “i” in X_j in the way prescribed above, we obtain:

$X_j=\sum_{i=0}^{n}s_{j,i} \cdot \Gamma^{i}+h_{j,n}\cdot\Gamma^{n+1}$

In other words, X_j becomes a sum of digits muliplied by powers of Γ i.e. it is expressed in the positional system.

It should be clear by now, why schools in the past insisted on memorizing a multiplication table. If you know the result of multiplication for every possible pair of digits, the execution of the procedure laid out above is faster.

Note that the multiplication table in the binary system is practically non existent:

0∙0=0, 0∙1=1∙0=0, 1∙1=1

Multiplying on fingers

There are many cleaver techniques of multiplying on fingers, so memorizing the multiplication table is not really that necessary. Let’s take a look at one of the techniques.

Example 1

We will multiply decimal 8 times 9.

In the first step we always subtract 5 from both numbers before adding them up, and the results is multiplied times ten so:

8-5=3 fingers of the left hand plus 9-5=4 fingers of the right hand is together 7. 7 times ten is 70.

In the second step we multiply the remaining fingers of the left hand: 5–3=2 times the remaining fingers of the right hand 5–4=1. The result is: 2∙1=2.

In the final step we add the results obtained in steps one and two: 70+2=72.

Example 2

Decimal 6∙7=?

The first step: ((6-5)+(7-5))∙10=(1+2)∙10=30

The second step: (5–1)∙(5–2)=4∙3=12

Together: 42

As a multiplication mnemonic, the algorithm described is useful for numbers in the range 5 to 10 decimal. We will prove its validity later.

Division procedure

How about division? Can we also reduce it from a head scratcher to a simple procedure? Let’s start with some examples.

Example 1

Let’s divide 1123 by 33, both expressed in the quinary system (the base equal to five).

To make it easier we could decompose 1123 into 100∙10+123 and divide 100 and 123 by 33 separately. This procedure is likely to generate the remainder of division for both, so afterwards we would have to add both remainders and divide the result by 33.

How about we take enough digits from the left of 1123 to make the resulting number the smallest one greater than 33. The first two digits are 11 and 11<33, so let’s grab another one: 112>33.

If we multiply 33 times 10 (five in the quinary system), the result is 330>112, so 112/33 must be between 1 and 4. Let’s guess it is 2:

33∙2=3∙10∙2+3∙2=3∙2∙10+(five+1)=(3∙2+1)∙10+1=(five+2)∙10+1=121

The guess was wrong 121>112. The correct answer must be 1 then:

112-1∙33=112-33=100+(1-3)∙10+(2-3)=10∙10+(0-3)∙10+(five+2-3)=

=five∙10+(0-3)∙10+4=(five+0-3)∙10+4=2∙10+4=24

so:

112=1∙33+24

thus:

1123=112∙10+3=(1∙33+24)∙10+3=10∙33+243

What’s left to do is the division 243/33. Again, 33∙10=330>243, so the result must be between 1 and 4. Let’s take a guess: 4.

33∙4=3∙4∙10+3∙4=3∙4∙10+(2∙five+2)=(3∙4+2)∙10+2=(2∙five+4)∙10+2=242

so:

243=4∙33+1

and the final result is:

1123=10∙33+4∙33+1=14∙33+1

Conclusion: we have replaced the problem of division 1123/33 with two other divisions: 112/33, 243/33. For both of them we knew that the result is somewhere between 1 and 4, so the division was easier to handle.

Example 2

Binary: 1101/101=?

110>101 so to simplify the task we can write: 1101=110∙10+1 and find 110/101 first.

110-1∙101=100+10-100-1=10-1=two-1=1

so:

110=1∙101+1

and

1101=(1∙101+1)∙10+1=10∙101+11

Done! For two binary numbers G>S, if G has the same number of digits or is one digit longer than S, then S fits into G only once. That makes the division of binary numbers super easy to perform!

What if G>S are not binary? Let’s assume they are given in the system with some arbitrary base Γ.

If G has the same number of digits as S then G/S<Γ because SΓ has more digits than G i.e. G<S∙Γ.

If G is one digit longer, yet its first digit from the left is smaller than the first digit from the left of S then again G/S<Γ because G<S∙Γ.

In situations when G is much greater than S, we can divide G into two parts:

$G=H_n\cdot\Gamma^n+L_n$

in such a way that L_n<Γⁿ and H_n is barely greater than S i.e. H_n/S<Γ.

Next, we perform the division H_n/S:

$H_n=g_n\cdot S+D_n$

where g_n is a digit and D_n is the remainder of division i.e. D_n<S. After inserting the above into the formula for G we get:

$G=(g_n\cdot S+D_n)\cdot\Gamma^n+L_n=(g_n\cdot\Gamma^n)\cdot S+(D_n\cdot\Gamma^n+L_n)$

If D_n∙Γⁿ+L_n is smaller than S, we are done, otherwise we need to divide it by S.

In the latter case, we start with decomposing D_n∙Γⁿ+L_n into:

$D_n\cdot\Gamma^n+L_n=H_k\cdot\Gamma^k+L_k$

where L_k<Γ^k and H_k/S<Γ.

Once it’s done, we perform H_k/S:

$H_k=g_k\cdot S+D_k$

where g_k is a digit and D_k<S. After inserting it back into the previous equation we get:

$D_n\cdot\Gamma^n+L_n=(g_k\cdot S+D_k)\cdot\Gamma^k+L_k=(g_k\cdot\Gamma^k)\cdot S+(D_k\cdot\Gamma^k+L_k)$

and after inserting the above into G, we finally have:

$G=(g_n\cdot\Gamma^n)\cdot S+(g_k\cdot\Gamma^k)\cdot S+(D_k\cdot\Gamma^k+L_k)$

If D_k∙Γ^k+L_k is smaller than S, we are done, otherwise we divide it by S, and we continue the procedure until the division G/S is completed.

Converting numbers from one positional system to the other

The last thing requiring our attention is converting numbers from one positional system to the other. Conversion from the system based on the base Γ₁ to the one with greater Γ₂ is straightforward and in fact we did it already in one of the previous sections.

To summarize, let’s take a look at some number N expressed in the positional system with the base Γ₁:

$N=\sum_{i=0}^{m}n_i\cdot\Gamma_1^i$

To turn it into the number in the system Γ₂>Γ₁, we simply write down Γ₁ and n_i using digits from the target system Γ₂ and perform multiplications and summations in the new system.

How about the conversion from the system based on Γ₁ into Γ₃ when Γ₁ > Γ₃ ? Let’s take a look at an example.

Example 1

Decimal 7 to binary i.e. Γ₁=ten > two=Γ₁?

7>2 so we don’t have enough digits in the binary system to use the same method as before.

If we divide 7/2 where 2 is the base of the binary system, the remainder of division must be smaller than 2 so it must be a binary digit:
7=3∙2+1

Ok then, let’s continue on this route and divide 3/2:
3=1∙2+1

Finally, after inserting the latter equation into the former one, we obtain:
7=(1∙2+1)∙2+1=1∙2∙2+1∙2+1

Lo and behold, that’s exactly what we are after. In this form it is trivial to transform 7 into the binary representation:

decimal 1∙2∙2+1∙2+1 is binary 1∙10∙10+1∙10+1=111

Example 2

Decimal 38 to the quinary.

38/5:
38=7∙5+3
3<5 so it is a digit in the quinary system.

7/5:
7=1∙5+2

so altogether:

38=(1∙5+2)∙5+3=1∙5∙5+2∙5+3

thus 38 in the quinary system reads:

1∙10∙10+2∙10+3=123

In general, if we want to convert number N from the system based on Γ₁ into Γ₃<Γ₁, first, we perform a division N / Γ₃:

$N=h_0\cdot\Gamma_3+d_0$

where d₀ is the remainder of division: d₀<Γ₃.

If h₀>Γ₃ then next, we find h₀ / Γ₃:

$h_0=h_1\cdot\Gamma_3+d_1$

where d₁<Γ₃ and we continue this process:

$h_1=h_2\cdot\Gamma_3+d_2$

until for some “n”, h_n-1 is not divisible by Γ₃. In other words:

$h_{n-1}=0\cdot\Gamma_3+d_n<\Gamma_3$

After inserting all these terms back into N, we get:

$N=\sum_{i=0}^{n}d_i\cdot\Gamma_3^i$

and we are done.

Computers and the binary system

Which of the positional systems is the easiest to implement in the form of an electronic counting machine?

For a binary system we simply need a single on/off (1/0) switch to store every digit. It is much simpler and less error prone than having to distinguish n>2 different states.

Also, binary addition pretty much boils down to: 0+0=0, 0+1=1+0=1, 1+1=10. Multiplication is equally simple. As we have seen, subtraction and division are also much simpler to perform than for any other positional system.

Looks like we have the answer why computers use the binary and not the decimal system!

Summary

In this chapter we have studied properties of natural numbers. The set containing them all is usually denoted with the symbol ℕ and the expression: x ∈ ℕ means: x is a member of ℕ.

ℕ contains infinite number of members, yet using a positional system every x ∈ ℕ can be expressed uniquely with a sequence of finite selection of symbols. Positional representation is also very convenient for performing basic mathematical operations: addition, subtraction, multiplication and division.

Addition and multiplication of natural numbers produce natural results and properties of these operations can be summarized with a handful of equations:

a+b=b+a, (a+b)+c=a+(b+c)

a∙b=b∙a, (a∙b)∙c=a∙(b∙c)

(a+b)∙c = a∙c + b∙c

Division and subtraction turned out to be more problematic. Division usually doesn’t produce a natural number and subtraction doesn’t always make sense. We will address the latter issue in the next chapter.