SP20:Lecture 14 Base b representation
We also introduced base b notation.
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.
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:
- The euclidean division algorithm
- The base b representation
- The Bézout coefficients
- The Proof:Cantor-Schroeder-Bernstein theorem
- The Prime factorization of a natural number
- most of the proofs] of existentially quantified statements.
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
We havePlugging this back in to the equation , 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 . 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:
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
No special notation is needed to indicate decimal, since that's how we normally interpret numbers. For example, means .
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 numbers are sometimes written with a leading "b", as in "b1101", which is another way of writing or .
- 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 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.