1.4 Definitions of elementary number theory
1.4.1 Even and odd
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.
Definition 1.3 An integer \(n\) is even exactly when there is an integer \(m\) such that \(n = 2m\).
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.”
Definition 1.4 An integer \(n\) is odd exactly when there is an integer \(m\) such that \(n = 2m + 1\).
1.4.2 Decimal and base-\(n\) notation
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 ten fingers. It is possible to use any positive integer in place of 10. In computer science, there are three 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.
Theorem 1.1 An integer is even if the units digit in its decimal representation is one of 0, 2, 4, 6 or 8.
Theorem 1.2 An integer is even if the units digit in its binary representation is 0.
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 favoured 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{align*} & 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{align*}\]
(Everything in the above derivation 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.
1.4.3 Divisibility
The notion of being even has an obvious generalization. Suppose that 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 (\(\mid\) 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\mid 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\mid n\) by
Definition 1.5 \(d \mid n\) exactly when \(\exists k \in {\mathbb Z}\) such that \(n = kd\).
In spoken language, the symbol \(d \mid 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\).
Nevertheless, by far the most popular way of expressing this concept is to just say “\(d\) divides \(n\).”
1.4.4 Floor and ceiling
Suppose that 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 that 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 three boxes and another seven-twelfths of a box. Obviously, we really need four 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:
Definition 1.6 \(y = \lfloor x \rfloor\) exactly when \(y \in {\mathbb Z}\) and \(y \leq x < y+1\).
Definition 1.7 \(y = \lceil x \rceil\) exactly when \(y \in {\mathbb Z}\) and \(y-1 < x \leq y\).
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.
1.4.5 Div and mod
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.A., 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 that 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:
Theorem 1.3 Given integers \(n\) and \(d>0\), there are unique integers \(q\) and \(r\) such that \(n = qd + r\) and \(0 \leq r < d\).
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 \; \operatorname{div} \;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 \[ n \equiv m \pmod{d}. \]
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: \[ x + y \bmod d = ( x \bmod d + y \bmod d ) \bmod d \] and \[ x \cdot y \bmod d = ( x \bmod d \cdot y \bmod d ) \bmod d. \]
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\).
1.4.6 Binomial coefficients
A “binomial” is a polynomial with two 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{align*} (a+b)^0 & = 1 \\ (a+b)^1 & = a+b \\ (a+b)^2 & = a^2 + 2ab + b^2 \\ \end{align*}\]To go much further than the second power requires a bit of work, but try to multiply \((a+b)\) and \((a^2 + 2ab + b^2)\) to determine \((a+b)^3\). If you feel up to it, take \((a^2 + 2ab + b^2)\) times itself to find \((a+b)^4\).
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 triangle10, which provides a convenient way to calculate small binomial coefficients. The first five rows of Pascal’s triangle (which are numbered 0 through 4 ).} are as follows: \[\begin{array}{ccccccccc} & & & & 1 & & & & \\ & & & 1 & & 1 & & & \\ & & 1 & & 2 & & 1 & & \\ & 1 & & 3 & & 3 & & 1 & \\ 1 & & 4 & & 6 & & 4 & & 1 \\ \end{array}\]
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.
Exercise 1.2 Add the next two rows to the Pascal triangle shown above.
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 \(\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 \(\binom{n}{k}\).
There is a formula for the binomial coefficients. Otherwise, we’d need to complete a pretty huge Pascal triangle in order to compute something like \(\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 \cdot 1)\).
The formula for a binomial coefficient is \[ \binom{n}{k} = \frac{n!}{k! \cdot (n-k)!}. \]
For example, \[ \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. \]
A slightly more complicated example (and one that gamblers are fond of) is \[\begin{align*} \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{align*}\]
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 five-card hand out of a deck of 52 cards.
Exercise 1.3 There are seven days in a week. In how many ways can one choose a set of three days (per week)?
1.4.7 Exercises
An integer \(n\) is doubly-even if it is even, and the integer \(m\) guaranteed to exist because \(n\) is even is itself even. Is 0 doubly-even? What are the first 3 positive, doubly-even integers?
Dividing an integer by two has an interesting interpretation when using binary notation: simply shift the digits to the right. Thus, \(22 = 10110_2\) when divided by two gives \(1011_2\) which is \(8+2+1=11\). How can you recognize a doubly-even integer from its binary representation?
The octal representation of an integer uses powers of 8 in place notation. The digits of an octal number run from 0 to 7, one never sees 8’s or 9’s. How would you represent 8 and 9 as octal numbers? What octal number comes immediately after \(777_8\)? What (decimal) number is \(777_8\)?
One method of converting from decimal to some other base is called repeated division. One divides the number by the base and records the remainder — one then divides the quotient obtained by the base and records the remainder. Continue dividing the successive quotients by the base until the quotient is smaller than the base. Convert 3267 to base-7 using repeated division. Check your answer by using the meaning of base-7 place notation. (For example \(54321_7\) means \(5\cdot7^4 + 4\cdot7^3 + 3 \cdot7^2 + 2\cdot7^1 + 1\cdot7^0\).)
State a theorem about the octal representation of even numbers.
In hexadecimal (base-16) notation, one needs 16 “digits,” the ordinary digits are used for 0 through 9, and the letters A through F are used to give single symbols for 10 through 15. The first 32 natural number in hexadecimal are: 1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,10,11,12,13,14,15,16,17,18,19,1A, 1B,1C,1D,1E,1F,20.
Write the next 10 hexadecimal numbers after AB.
Write the next 10 hexadecimal numbers after FA.
For conversion between the three bases used most often in computer science, we can take binary as the “standard” base and convert using a table look-up. Each octal digit will correspond to a binary triple, and each hexadecimal digit will correspond to a 4-tuple of binary numbers. Complete the following tables. (As a check, the 4-tuple next to \(A\) in the table for hexadecimal should be 1010 — which is nice since \(A\) is really 10 so if you read that as “ten-ten” it is a good aid to memory.) \[\begin{array}{ccc} \begin{array}{|c|c|} \hline \text{octal} & \text{binary} \\ \hline \hline 0 & 000 \\ \hline 1 & 001 \\ \hline 2 & \\ \hline 3 & \\ \hline 4 & \\ \hline 5 & \\ \hline 6 & \\ \hline 7 & \\ \hline \end{array} & ~~~~~ & \begin{array}{|c|c|} \hline \text{hexadecimal} & \text{binary} \\ \hline \hline 0 & 0000 \\ \hline 1 & 0001 \\ \hline 2 & 0010 \\ \hline 3 & \\ \hline 4 & \\ \hline 5 & \\ \hline 6 & \\ \hline 7 & \\ \hline 8 & \\ \hline 9 & \\ \hline \mathsf{A} & \\ \hline \mathsf{B} & \\ \hline \mathsf{C} & \\ \hline \mathsf{D} & \\ \hline \mathsf{E} & \\ \hline \mathsf{F} & \\ \hline \end{array} \end{array}\]
Use the tables from the previous problem to make the following conversions.
Convert \(757_8\) to binary.
Convert \(1007_8\) to hexadecimal.
Convert \(100101010110_2\) to octal.
Convert \(1111101000110101_2\) to hexadecimal.
Convert \(\mathsf{FEED}_{16}\) to binary.
Convert \(\mathsf{FFFFFF}_{16}\) to octal.
Try the following conversions between various number systems:
Convert \(30\) (base 10) to binary.
Convert \(69\) (base 10) to base 5.
Convert \(1222_3\) to binary.
Convert \(1234_7\) to base 10.
Convert \(\mathsf{EEED}_{15}\) to base 12.
(Use \(\{1, 2, 3 \ldots 9, d, e\}\) as the digits in base 12.)
Convert \(678_{9}\) to hexadecimal.
It is a well known fact that if a number is divisible by 3, then 3 divides the sum of the (decimal) digits of that number. Is this result true in base 7? Do you think this result is true in any base?
Suppose that 340 pounds of sand must be placed into bags having a 50 pound capacity. Write an expression using either floor or ceiling notation for the number of bags required.
True or false? \[ \left\lfloor \frac{n}{d}\right\rfloor < \left\lceil \frac{n}{d}\right\rceil \]
What is the value of \(\lceil\pi\rceil^{2}-\lceil\pi^{2}\rceil\)?
Assuming the symbols \(n\), \(d\), \(q\), and \(r\) have meanings as in the quotient-remainder theorem (Theorem 1.3). Write expressions for \(q\) and \(r\), in terms of \(n\) and \(d\) using floor and/or ceiling notation.
Calculate the following quantities:
\(3 \bmod 5\)
\(37 \bmod 7\)
\(1000001 \bmod 100000\)
\(6 \; \operatorname{div} \;6\)
\(7 \; \operatorname{div} \;6\)
\(1000001 \; \operatorname{div} \;2\)
Calculate the following binomial coefficients:
\(\displaystyle\binom{3}{0}\)
\(\displaystyle\binom{7}{7}\)
\(\displaystyle\binom{13}{5}\)
\(\displaystyle\binom{13}{8}\)
\(\displaystyle\binom{52}{7}\)
An ice cream shop sells the following flavours: chocolate, vanilla, strawberry, coffee, butter pecan, mint chocolate chip and raspberry. How many different bowls of ice cream — with three scoops — can they make?
This triangle was actually known well before Blaise Pascal began to study it, but it carries his name today.↩