We will describe and define the base b representation of a natural number. At the end of lecture, we introduced notation for divisibility and the definition of a greatest common divisor.

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:

Definition: Base b interpretation

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.

Definition: Base b representation

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 [math]d_2 = 7, d_1 = 3, d_0 = 2 [/math] 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 [math]n [/math] be a base b number", any more than it makes sense to say "let [math]n [/math] be a number in roman numerals". The object [math]596 [/math] '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, [math]1234 [/math] 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 [math](1101)_2 [/math] or [math]13 [/math].

Hexadecimal

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, [math]0x2c [/math] is another way of writing [math](2c)_{16} [/math], which is another way of writing [math]44 [/math].

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 [math]122 [/math].

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.

Base b arithmetic

You are already familiar with several digit-by-digit algorithms for working with decimal numbers, such as long addition, long multiplication, and long division.

It turns out that these algorithms also work in base b; one just needs to represent digits in base [math]b [/math]. For example, to add [math](124)_7 [/math] and [math](66)_7 [/math], we can add them digit by digit, starting from the right, and handling carries appropriately. We would add 6 and 4 to get the number 10, which is represented by [math](13)_7 [/math]; we would keep the 3 and carry the 1. We would then add the carry and the second digits to get [math]2 + 6 + 1 = 9 = (12)_7 [/math]; again we keep the 2 and carry the 1. Finally we add the third digit and the carry to get the third digit 2; this gives us .

	1	2	4
+		6	6	(base 7)
	2	2	3

You could prove that these algorithms all work using induction.

Existence of base b representation

Claim (see proof):

For all and , there exists a sequence of digits satisfying .

Uniqueness of base b representation

As usual, in order to justify calling the base b representation of [math]a [/math] "the" base b representation, we need to prove that it is unique. In fact, it is not necessarily unique if we allow leading 0's (for example, [math](0123)_{10} = (123)_{10} [/math]), but if we rule them out, then we have the following fact:

Claim (see proof):

For all , if and if and if then .

The proof is left as an exercise. Use induction on [math]k [/math] and the fact that The quotient and remainder are unique.

Divisibility and gcd

In the following lecture, we will give an algorithm for finding the greatest common divisor; here we introduce a few necessary definitions:

Definition: Divides

If and are integers, we say that divides (written "") if there exists an integer satisfying .

If we also say that [math]a [/math] is a divisor (or factor) of [math]b [/math].

Definition: Greatest common divisor

If , then the greatest common divisor of and satisfies:

and (i.e. [math]g [/math] is a common divisor), and
for any [math]c [/math] that divides both [math]a [/math] and [math]b [/math], we have [math]c ≤ g [/math] (in other words, [math]g [/math] is greater than any other common divisor). In fact we will show that (which implies that [math]c ≤ g [/math]).

FA18:Lecture 14 Base b

Contents