# SP20:Lecture 14 Base b representation

($1)$2 | $3 ($4) | $5 ($6)

We proved the existence and uniqueness of Euclidean division (division with quotient and remainder).

We also introduced base b notation.

# Euclidean division

While studying number theory, we will be primarily interested in the properties of the integers and natural numbers. This means that if we want to write something like "", we'll have to be very careful to check that divides . This makes everything very complicated, so instead, we'll avoid dividing natural numbers.

We can, however, do division with remainder. The Euclidean division algorithm is just a fancy way of saying this:

For all and all , there exists numbers and such that

Here and are the quotient and remainder of over :

Definition: Quotient
We say is a quotient of over if for some with . We write (note that quot is a well defined function).
Definition: Remainder
We say is a remainder of over if for some and . We write (note that rem is a well defined function).

Note that all this is a theorem, it is called the "Euclidean division algorithm" because its proof contains an algorithm.

Proof:
We prove this by weak induction on . Let be the statement "for all , there exists satisfying (1) and (2) above." We will show and assuming .

Base case: We want to show P(0). Let . Then and since .

Inductive step: Assume ; we want to show . By , we know that there exists numbers and such that . We want to show that there exists numbers and such that .

Since , we know that either or . In the former case, we can let and . Then (and clearly ).

In the latter case, we can let and . Then . Again it is clear that .

In either case, we have shown that there exist and satisfying (1) and (2), as required.

## Proofs and algorithms

Most proofs that something exists give you instructions for finding it. For example, inside the proof that the quotient and remainder exist, is an algorithm for finding them: If , follow the instructions in the base case; if , then first find the quotient q' and remainder r' for and , then follow the instructions in the inductive step. Of course, while we are finding and , we may need to also find the quotient and remainder of and , and so on.

We will cover several examples of such algorithms/proofs:

In fact, there are whole programming languages where instead of writing a program, you write a proof; after the computer checks your proof, it extracts a program for you (which is guaranteed to be correct!).

## Uniqueness of euclidean division

In order to justify calling quotients and remainders "the quotient" or "the remainder", we should check that they are unique. This is justified by the following claim:

For any and , if and are a quotient and remainder of and (that is, if and ), and if and are also a quotient and remainder of over , then and .
Proof:
Assume that and and that both and are between 0 and . We want to show that and .

We have , so . This means that is a multiple of ; it could be any of . However, since we have and , we have . Thus, the only possible value of is 0, so .

Plugging this back in to the equation shows that either or . Since we have defined the quotient and remainder by , we must have , so and thus .

# Base b representation

When we write down sequences of digits in decimal (or base 10) notation, we interpret them according to a formula. For example, we interpret the number 1234 as a 1 in the "thousands place", a 2 in the "hundreds place", a 3 in the "tens place", and a 4 in the "ones place". In other words, we interpret the string of digits "1234" as .

It is occasionally useful to write a similar formula, but with a different set of possible digits. We have the following definitions:

If are all natural numbers satisfying for all , then the base b interpretation of , written is given by

For example, .

Definition: Digit
numbers satisfying are called base b digits.
If is a sequence of base digits, and if , then we say that is the Base b representation of

For example, the base 9 representation of 596 is the sequence of digits because .

Note that the base is not an intrinsic property of a natural number, but rather is a property of the way we write the number down. It does not make sense to say something like "let be a base b number", any more than it makes sense to say "let be a number in roman numerals". The object 'is' the same as the object (and also the object ); it is just written down in three different ways.

## Common number bases

### Decimal

The most common number base is base 10, or decimal. This is how we usually interpret numbers. It is convenient because most people have ten fingers and that's how we first learn to count.

No special notation is needed to indicate decimal, since that's how we normally interpret numbers. For example, means .

### Binary

In digital logic, it is convenient to represent numbers using high and low voltages; We can think of a high voltage as "1" and a low voltage as "0"; allowing us two digits to work with. Thus it is convenient to represent numbers in base 2, which is also called binary.

Binary digits are also called bits.

Binary numbers are sometimes written with a leading "b", as in "b1101", which is another way of writing or .

Hexadecimal is another word for base 16. It is useful for a few reasons:

• In decimal, dividing by 10 and taking the remainder are very easy operations: the quotient is represented by all the digits but the last, while the remainder is represented by the last. Dividing by 100 and other powers of 10 is similarly easy. In some applications, it is useful to be able to easily divide by 16 (or other high powers of 2), and this is easier to do by humans if the numbers are written down in base 16.
• A single hexadecimal digit is a number that can be represented by 4 bits, so it is easier to translate between hexadecimal and binary than it is between other number bases.

In order to represent numbers in hexadecimal, we need digits to represent the numbers between ten and fifteen. People usually use the letters a–f for this purpose, with a standing for 10, b for 11, etc.

Hexadecimal numbers are often prefixed with a "0x". For example, is another way of writing , which is another way of writing .

### Octal

Octal is another word for base 8. It is useful for the same reasons as hexadecimal notation, although it is less commonly used. Some programming languages allow you to write a number in octal notation by prefixing it with a 0 as in "0172" which (in some contexts) would be interpreted as or .

### Ascii and Unicode

Computers are good at processing numbers, but a lot of what we process are strings of characters. By numbering each possible character, we can use Base b interpretation and Base b representation to convert from strings of characters to natural numbers and back.

ASCII and Unicode are two ways to assign a digit to each character. ASCII stands for the "American standard code for information interchange"; it is just a table mapping 128 characters (e.g. 'A', 'B', 'a', 'b', '!', '0', ')', etc) to the base 128 digits.

Unicode is the same idea, except that there are 1,114,112 unicode characters in the table (including things like '∧', '∃', '喂', '😀', '🐱', and '💩'). You can think of unicode as a way to write down numbers in base 1,114,112.

Because base b representation is a bijection (since every number has a base b representation and the base b representation is unique), we will simply treat strings as numbers and vice-versa without paying much more attention to it.