Number systems

Prerequisite: Division with remainder

Consider an integer number . Then, using the division with remainder theorem we know that for any integer there is a unique division with remainder: where .

Let’s take . Then the equality turns into where .

Then let’s iterate this procedure by dividing by with remainder: . Then

where both and belong to the set .

After each division with remainder the quotient gets smaller and smaller: eventually it will become smaller than , and the next will be . Let’s say that the smaller than has number . Then , and all subsequent ‘s are .

We will then get that

We just defined the decimal system! The numbers are the digits of in the decimal system.

Observation

The same procedure can be applied for any natural ! This procedure actually allows us to define number systems base any natural number. Moreover, it can be performed for any non-zero integer , but the output is less intuitive for negative numbers.

Exercise

Decompose the number as with the same restrictions for the ‘s:

Let’s restate the result obtained above:

Theorem

Given a non-zero integer number . For all integer numbers there is a unique way to rewrite as a sum of the following form:

Question

Try to re-prove why is the rewriting unique. If you struggle with this, review the uniqueness proof in the division with remainder theorem.

We are now ready to state the definition of a positional number system:

Definition (positional number system)

Given a integer called the base. For any number we will call ” base ” the decomposition . The numbers are called digits. The used notation is

The upper bar is to emphasize that the participating letters are digits whereas the subscript specifies the base. The bar is usually ignored when it is clear that the participating symbols are being written as digits instead of multiplicated.

Example

(check!)

Observation

When you run out of conventional notations for digits. Usually the sequence of digits is extended by letters alphabetically. For example, the digits base are commonly written as .

Problem 1

What is in base notation? What is ? What about ?

The most common bases used are , , , , and, in more subtle ways, . Powers of mainly occur from computer science. For example, any number from to , a total of possibilities (the number of states encoded by bits) would be rewritten by an (at most) two-digit number base : .

Problem 2

Rewrite the numbers , and in base .