If you divide a number by 2 and it comes out even (i.e. with no remainder) the number is said to be even. So the word even is related to division. It turns out that the concept even is better understood through thinking about multiplication.

You should note that there is a “two-way street” sort of quality to this definition — indeed with most, if not all, definitions. If a number is even, then we are guaranteed the existence of another integer half as big. On the other hand, if we can show that another integer half as big exists, then we know the original number is even. This two-wayness means that the definition is what is known as a biconditional, a concept which we'll revisit in Section 2.2.

A lot of people don't believe that \(0\) should be counted as an even number. Now that we are armed with a precise definition, we can answer this question easily. Is there an integer \(x\) such that \(0 = 2x\) ? Certainly! let \(x\) also be \(0\). (Notice that in the definition, nothing was said about \(m\) and \(n\) being distinct from one another.)

An integer is odd if it isn't even. That is, amongst integers, there are only two possibilities: even or odd. We can also define oddness without reference to “even.”

You can also identify even numbers by considering their decimal representation. Recall that each digit in the decimal representation of a number has a value that depends on its position. For example, the number \(3482\) really means \(3\cdot10^3 + 4\cdot10^2 + 8\cdot10^1 + 2\cdot10^0\). This is also known as place notation. The fact that we use the powers of 10 in our place notation is probably due to the fact that most humans have 10 fingers. It is possible to use any number in place of 10. In Computer Science there are 3 other bases in common use: 2, 8 and 16 — these are known (respectively) as binary, octal and hexadecimal notation. When denoting a number using some base other than 10, it is customary to append a subscript indicating the base. So, for example, \(1011_2\) is binary notation meaning \(1\cdot2^3 + 0\cdot2^2 + 1\cdot2^1 + 1\cdot2^0\) or \(8+2+1 = 11\). No matter what base we are using, the rightmost digit of the number multiplies the base raised to the \(0\)-th power. Any number raised to the \(0\)-th power is 1, and the rightmost digit is consequently known as the units digit. We are now prepared to give some statements that are equivalent to our definition of even. These statements truly don't deserve the designation “theorem,” they are immediate consequences of the definition.

For certain problems it is natural to use some particular notational system. For example, the last theorem would tend to indicate that binary numbers are useful in problems dealing with even and odd. Given that there are many different notations that are available to us, it is obviously desirable to have means at our disposal for converting between them. It is possible to develop general rules for converting a base-\(a\) number to a base-\(b\) number (where \(a\) and \(b\) are arbitrary) but it is actually more convenient to pick a “standard” base (and since we're human we'll use base-\(10\)) and develop methods for converting between an arbitrary base and the “standard” one. Imagine that in the not-too-distant future we need to convert some numbers from the base-\(7\) system used by the Seven-lobed Amoebazoids from Epsilon Eridani III to the base-\(12\) scheme favored by the Dodecatons of Alpha-Centauri IV. We will need a procedure for converting base-\(7\) to base-\(10\) and another procedure for converting from base-\(10\) to base-\(12\). In the School House Rock episode “Little Twelve Toes” they describe base-\(12\) numeration in a way that is understandable for elementary school children — the digits they use are \(\{1, 2, 3, 4, 5, 6, 7, 8, 9, \delta, \epsilon \}\), the last two digits (which are pronounced “dec” and “el”) are necessary since we need single symbols for the things we ordinarily denote using \(10\) and \(11\).

Converting from some other base to decimal is easy. You just use the definition of place notation. For example, to find what \(451663_7\) represents in decimal, just write \begin{equation*} 4 \cdot 7^5 + 5 \cdot 7^4 + 1 \cdot 7^3 + 6 \cdot 7^2 + 6 \cdot 7 + 3 = 4 \cdot 16807 + 5 \cdot 2401 + 1 \cdot 343 + 6 \cdot 49 + 6 \cdot 7 + 3 = 79915. \end{equation*}

(Everything in the line above can be interpreted as a base-\(10\) number, and no subscripts are necessary for base-\(10\).)

Converting from decimal to some other base is harder. There is an algorithm called “repeated division” that we'll explore a bit in the exercises for this section. For the moment, just verify that \(3\delta 2\epsilon 7_{12}\) is also a representation of the number more conventionally written as 79915.

The notion of being even has an obvious generalization. Suppose we asked whether \(3\) divided evenly into a given number. Presumably we could make a definition of what it meant to be threeven, but rather than doing so (or engaging in any further punnery) we shall instead move to a general definition. We need a notation for the situation when one number divides evenly into another. There are many ways to describe this situation in English, but essentially just one in “math,” we use a vertical bar — not a fraction bar. Indeed the difference between this vertical bar and the fraction symbol (\(\divides\) versus \(/\)) needs to be strongly stressed. The vertical bar when placed between two numbers is a symbol which asks the question “Does the first number divide evenly (i.e. with no remainder) into the second?” On the other hand the fraction bar asks you to actually carry out some division. The value of \(2\divides 5\) is false, whereas the value of \(2/5\) is \(.4\)

As was the case in defining even, it turns out that it is best to think of multiplication, not division, when making a formal definition of this concept. Given any two integers \(n\) and \(d\) we define the symbol \(d\divides n\) by

In spoken language the symbol \(d \divides n\) can be translated in a variety of ways:

• \(d\) is a divisor of \(n\).

• \(d\) divides \(n\) evenly.

• \(d\) is a factor of \(n\).

• \(n\) is an integer multiple of \(d\).

Although, by far the most popular way of expressing this concept is to just say “\(d\) divides \(n\).”

Suppose there is an elevator with a capacity of 1300 pounds. A large group of men who all weigh about 200 pounds want to ascend in it. How many should ride at a time? This is just a division problem, 1300/200 gives 6.5 men should ride together. Well, obviously putting half a person on an elevator is a bad idea — should we just round-up and let 7 ride together? Not if the 1300 pound capacity rating doesn't have a safety margin! This is an example of the kind of problem in which the floor function is used. The floor function takes a real number as input and returns the next lower integer.

Suppose after a party we have 43 unopened bottles of beer. We'd like to store them in containers that hold 12 bottles each. How many containers will we need? Again, this is simply a division problem — \(43/12 = 3.58\overline{333}\). So we need 3 boxes and another 7 twelfths of a box. Obviously we really need 4 boxes — at least one will have some unused space in it. In this sort of situation we're dealing with the ceiling function. Given a real number, the ceiling function rounds it up to the next integer.

Both of these functions are denoted using symbols that look very much like absolute value bars. The difference lies in some small horizontal strokes.

If \(x\) is a real number, its floor is denoted \(\lfloor x \rfloor\), and its ceiling is denoted \(\lceil x \rceil\). Here are the formal definitions:

Basically, the definition of floor says that \(y\) is an integer that is less than or equal to \(x\), but \(y+1\) definitely exceeds \(x\). The definition of ceiling can be paraphrased similarly.

In the next section we'll discuss the so-called division algorithm — this may be over-kill since you certainly already know how to do division! Indeed, in the U.S., long division is usually first studied in the latter half of elementary school, and division problems that don't involve a remainder may be found as early as the first grade. Nevertheless, we're going to discuss this process in sordid detail because it gives us a good setting in which to prove relatively easy statements. Suppose you are setting-up a long division problem in which the integer \(n\) is being divided by a positive divisor \(d\). (If you want to divide by a negative number, just divide by the corresponding positive number and then throw an extra minus sign on at the end.)

Recall that the answer consists of two parts, a quotient \(q\), and a remainder \(r\). Of course, \(r\) may be zero, but also, the largest \(r\) can be is \(d-1\). The assertion that this answer uniquely exists is known as the quotient-remainder theorem:

The words “div” and “mod” that appear in the title of this subsection provide mathematical shorthand for \(q\) and \(r\). Namely, “\(n \bmod d\)” is a way of expressing the remainder \(r\), and “\(n \tdiv d\)” is a way of expressing the quotient \(q\).

If two integers, \(m\) and \(n\), leave the same remainder when you divide them by \(d\), we say that they are congruent modulo \(d\). One could express this by writing \(n \bmod d = m \bmod d\), but usually we adopt a shorthand notation \begin{equation*} n \equiv m \pmod{d}. \end{equation*}

If one is in a context in which it is completely clear what \(d\) is, it's acceptable to just write \(n \equiv m\).

The “mod” operation is used quite a lot in mathematics. When we do computations modulo some number \(d\), (this is known as “modular arithmetic” or, sometimes, “clock arithmetic”) some very nice properties of “mod” come in handy: \begin{equation*} x + y \bmod d = ( x \bmod d + y \bmod d ) \bmod d \end{equation*} and \begin{equation*} x \cdot y \bmod d = ( x \bmod d \cdot y \bmod d ) \bmod d. \end{equation*}

These rules mean that we can either do the operations first, then reduce the answer \(\bmod\; d\) or we can do the reduction \(\bmod\; d\) first and then do the operations (although we may have to do one more round of reduction \(\bmod\; d\)).

For example, if we are working \(\bmod\; 10\), and want to compute \(87 \cdot 96 \bmod\; 10\), we can instead just compute \(7 \cdot 6 \bmod\; 10\), which is \(2\).

A “binomial” is a polynomial with 2 terms, for example \(x+1\) or \(a+b\). The numbers that appear as the coefficients when one raises a binomial to some power are — rather surprisingly — known as binomial coefficients.

Let's have a look at the first several powers of \(a+b\). \begin{gather*} (a+b)^0 = 1\\ (a+b)^1 = a+b\\ (a+b)^2 = a^2 + 2ab + b^2 \end{gather*}

To go much further than the second power requires a bit of work, but try the following

Since we're interested in the coefficients of these polynomials, it's important to point out that if no coefficient appears in front of a term that means the coefficient is 1.

These binomial coefficients can be placed in an arrangement known as Pascal's triangle ¹This triangle was actually known well before Blaise Pascal began to study it, but it carries his name today., which provides a convenient way to calculate small binomial coefficients

Notice that in the triangle there is a border on both sides containing 1's and that the numbers on the inside of the triangle are the sum of the two numbers above them. You can use these facts to extend the triangle.

Binomial coefficients are denoted using a somewhat strange looking symbol. The number in the \(k\)-th position in row number \(n\) of the triangle is denoted \(\displaystyle \binom{n}{k}\). This looks a little like a fraction, but the fraction bar is missing. Don't put one in! It's supposed to be missing. In spoken English you say “\(n\) choose \(k\)” when you encounter the symbol \(\displaystyle \binom{n}{k}\).

There is a formula for the binomial coefficients — which is nice. Otherwise we'd need to complete a pretty huge Pascal triangle in order to compute something like \(\displaystyle \binom{52}{5}\). The formula involves factorial notation. Just to be sure we are all on the same page, we'll define factorials before proceeding.

The symbol for factorials is an exclamation point following a number. This is just a short-hand for expressing the product of all the numbers up to a given one. For example \(7!\) means \(1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7\). Of course, there's really no need to write the initial \(1\) — also, for some reason people usually write the product in decreasing order (\(7! = 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2)\).

The formula for a binomial coefficient is \begin{equation*} \binom{n}{k} = \frac{n!}{k! \cdot (n-k)!}. \end{equation*}

For example \begin{equation*} \binom{5}{3} = \frac{5!}{3! \cdot (5-3)!} = \frac{1\cdot 2\cdot 3\cdot 4\cdot 5}{(1\cdot 2\cdot 3) \cdot (1\cdot 2)} = 10. \end{equation*}

A slightly more complicated example (and one that gamblers are fond of) is \begin{gather*} \binom{52}{5} = \frac{52!}{5! \cdot (52-5)!} = \frac{1\cdot 2\cdot 3\cdot \cdots 52}{(1\cdot 2\cdot 3 \cdot 4 \cdot 5) \cdot (1\cdot 2 \cdot 3\cdot \cdots 47)}\\ = \frac{48 \cdot 49 \cdot 50 \cdot 51 \cdot 52}{1\cdot 2\cdot 3 \cdot 4 \cdot 5} = 2598960. \end{gather*}

The reason that a gambler might be interested in the number we just calculated is that binomial coefficients do more than just give us the coefficients in the expansion of a binomial. They also can be used to compute how many ways one can choose a subset of a given size from a set. Thus \(\binom{52}{5}\) is the number of ways that one can get a 5 card hand out of a deck of 52 cards.