Definition. A set is an unordered collection of distinct objects. The objects in a set are called the elements, or members, of the set. A set is said to contain its elements.
A set can be defined by simply listing its members inside curly braces. For example, the set ${2, 4, 17, 23}$ is the same as the set ${17, 4, 23, 2}$. To denote membership we use the $\in$ symbol, as in $4 \in {2, 4, 17, 23}$. On the other hand, non-membership is denoted as in $5 \notin {2, 4, 17, 23}$.
If we want to specify a long sequence that follows a pattern, we can use the ellipsis notation, meaning “fill in, using the same pattern.” The ellipsis is often used after two or more members of the sequence, and before the last one, as follows: ${1, 2, \ldots, n}$. The pattern denoted by the ellipsis should be apparent at first sight! For instance, ${1, \ldots, n}$ is generally regarded as underspecified (that is, too ambiguous). Of course, even ${1, 2, \ldots, n}$ is still ambiguous—did we mean all integers between 1 and n, all powers of two up to n, or perhaps the set ${1, 2, 25, n}$?—but is generally sufficient, unless you really do mean all powers of two up to n, in which case ${2^0, 2^1, 2^2, \ldots, 2^k}$ for an appropriate $k$ is a better choice. The ellipsis can also be used to define an infinite set, as in the following.
Definition. The set of natural numbers or nonnegative integers, denoted by $\mathbb{N}$, is defined as ${0, 1, 2, \ldots}$.
To avoid ambiguities it is often useful to use the set builder notation, which lists on the right side of the colon the property that any set element, specified on the left side of the colon, has to satisfy. Let’s define the positive integers using the set builder notation:
\[\mathbb{N}^+ = \{x : x \in \mathbb{N} \text{ and } x > 0\}.\]We can also write
\[\mathbb{N}^+ = \{x \in \mathbb{N} : x > 0\}.\]This is a matter of taste. In general, use the form that will be easiest for the reader of your work to understand. Often it is the least “cluttered” one.
Ok, now onto the integers:
\[\mathbb{Z} = \{x : x \in \mathbb{N} \text{ or } -x \in \mathbb{N}\}.\]Hmm, perhaps in this case it is actually better to write
\[\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}.\]Remember, when you write mathematics, you should keep your readers’ perspective in mind. For now, we—the staff of this course—are your readers. In the future it might be your colleagues, supervisors, or the readers of your published work. In addition to being reasonably formal and unambiguous, your mathematical writing should be as clear and understandable to your intended readership as possible.
Here are the rational numbers:
\[\mathbb{Q} = \left\{\frac{a}{b} : a \in \mathbb{Z}, b \in \mathbb{Z}, b \neq 0\right\}.\]Instead of $a \in \mathbb{Z}, b \in \mathbb{Z}$, you can write $a, b \in \mathbb{Z}$, which is more concise and generally more readable. Don’t go overboard, though, with writing something like $a, b \neq 0 \in \mathbb{Z}$, this is way too confusing and does not say what you want it to.
Finally, the set of real numbers is denoted by $\mathbb{R}$. All the reals that are not rational are called irrational. These include the familiar $\pi = 3.1415926\ldots$, $e = 2.7182818\ldots$, $\sqrt{2}$, and infinitely many others. (How do we know that these numbers are irrational, do you ask? Actually, we will see a proof of this for $\sqrt{2}$ shortly. The proofs for $\pi$ and $e$ require mathematical analysis and are outside our scope.)
A is said to be a subset of B if and only if every element of A is also an element of B, in which case we write $A \subseteq B$. A is a strict subset of B if A is a subset of B and A is not equal to B, which is denoted by $A \subset B$. For example, ${4, 23} \subset {2, 4, 17, 23} \subseteq {2, 4, 17, 23}$.
Two sets A and B are considered equal if and only if they have the same elements. This is denoted by $A = B$. More formally, $A = B$ if and only if $A \subseteq B$ and $B \subseteq A$.
For two sets A and B, the operations of union, intersection, and difference are defined as follows:
\[A \cup B = \{x : x \in A \text{ or } x \in B\}\] \[A \cap B = \{x : x \in A \text{ and } x \in B\}\] \[A \setminus B = \{x : x \in A \text{ and } x \notin B\}\]The $\cup$ and $\cap$ notation can be extended to the union and intersection of multiple sets. Given n sets $A_1, A_2, \ldots, A_n$, we can write
\[\bigcup_{i=1}^n A_i\]for their union, and
\[\bigcap_{i=1}^n A_i\]for their intersection. In fact, this notation is pretty flexible and the same union can be written as
\[\bigcup_{i=1}^n A_i = \bigcup_{1 \le i \le n} A_i = \bigcup_{i \in \{x : 1 \le x \le n\}} A_i.\]Here is another example:
\[\bigcap_{\substack{i \in \{x : 1 \le x \le 10\} \\ i \text{ is prime}}} A_i = A_2 \cap A_3 \cap A_5 \cap A_7.\]Given a set A, the cardinality of A, also known as the size of A, is simply the number of elements in A. The cardinality of A is denoted by $|A|$. For example, if $A = {2, 4, 17, 23}$, then $|A| = 4$.
The empty set is denoted by $\emptyset$. It is the unique set without elements. It holds that $\emptyset \subseteq A$ for any set A. Why? By definition, this holds if every element of $\emptyset$ is also an element of A. Since $\emptyset$ has no elements, all possible statements about the elements of $\emptyset$ are true! In particular, all elements of $\emptyset$ are also elements of A. If this is confusing don’t worry, we will go into such matters more rigorously when we get to logic. (For now, you can ponder the following: If we know for a fact that there are no unicorns, then it is definitely true that all unicorns have soft light-blue fur.)
A set can contain sets as its elements. For example, ${{2, 4}, {17}, 23}$ is a perfectly valid set with three elements, two of them sets. (The second element is a singleton, a set with one element.) Note that ${2, 4} \in {{2, 4}, {17}, 23}$, but ${2, 4} \subseteq {2, 4, 17, 23}$, and that $17 \notin {{2, 4}, {17}, 23}$, but ${17} \in {{2, 4}, {17}, 23}$. Also, ${\emptyset}$ is not the empty set. (Think about it.)
The power set of a set A is the set of all subsets of A, and is denoted by $2^A$. That is,
\[2^A = \{S : S \subseteq A\}.\]For example, for $A = {2, 4, 17, 23}$, we have
\[2^A = \{\emptyset, \{2\}, \{4\}, \{17\}, \{23\}, \{2, 4\}, \{2, 17\}, \{2, 23\}, \{4, 17\}, \{4, 23\}, \{17, 23\}, \{2, 4, 17\}, \{2, 4, 23\}, \{2, 17, 23\}, \{4, 17, 23\}, \{2, 4, 17, 23\}\}.\]The cardinality of this set is 16, and $16 = 2^4$. This is not a coincidence: As we shall see when we get to combinatorics and counting, for a set A with n elements, the cardinality of $2^A$ is $2^n$. This is in fact the reason for the power set notation.
Suppose there is an infinite line of people, numbered 1, 2, 3, . . ., and every person has been instructed as follows: “If something is whispered in your ear, go ahead and whisper the same thing to the person in front of you (the one with the greater number)”. Now, what will happen if we whisper a secret to person 1? 1 will tell it to 2, 2 will tell it to 3, 3 will tell it to 4, and … everybody is going to learn the secret! Similarly, suppose we align an infinite number of dominoes, such that if some domino falls, the next one in line falls as well. What happens when we knock down the first domino? That’s right, they all fall. This intuition is formalized in the principle of mathematical induction:
Induction Principle: Given a set A of positive integers, suppose the following hold:
Then all positive integers belong to A. (That is, A = $\mathbb{N}^+$.)
Here are two simple proofs that use the induction principle:
Theorem 2.1.1. Every positive integer is either even or odd.
Proof. By definition, we are required to prove that for every $n \in \mathbb{N}^+$, there exists some $l \in \mathbb{N}$, such that either $n = 2l$ or $n = 2l + 1$. The proof proceeds by induction. The claim holds for $n = 1$, since $1 = 2 \cdot 0 + 1$. Suppose the claim holds for $n = k$. That is, there exists $l \in \mathbb{N}$, such that $k = 2l$ or $k = 2l + 1$. We prove that the claim holds for $n = k + 1$. Indeed, if $k = 2l$ then $k + 1 = 2l + 1$, and if $k = 2l + 1$ then $k + 1 = 2(l + 1)$. Thus the claim holds for $n = k + 1$ and the proof by induction is complete.
Theorem 2.1.2. Every positive integer power of 3 is odd.
Proof. By definition, we are required to prove that for every $n \in \mathbb{N}^+$, it holds that $3^n = 2l + 1$, for some $l \in \mathbb{N}$. The proof proceeds by induction. For $n = 1$, we have $3 = 2 \cdot 1 + 1$, so the claim holds. Suppose the claim holds for $k$, so $3^k = 2l + 1$, for some $l \in \mathbb{N}$. Then
\[3^{k+1} = 3 \cdot 3^k = 3(2l + 1) = 2(3l + 1) + 1,\]and the claim also holds for $k + 1$. The proof by induction is complete.
Proof tip: If you don’t know how to get a proof started, look to the definitions, and state formally and precisely what it is that you need to prove. It might not be obvious how to prove that “Every positive integer power of 3 is odd”, but a bit easier to proceed with proving that “for every $n \in \mathbb{N}^+$, it holds that $3^n = 2l + 1$, for some $l \in \mathbb{N}$.” If you need to prove an implication (that is, a claim of the form “if . . . then . . .”), then formally state all the assumptions as well as what you need to prove that they imply. Comparing the two might lead to some insight.
Proof technique: Induction. The induction principle is often used when we are trying to prove that some claim holds for all positive integers. As the above two proofs illustrate, when we use induction we do not need to explicitly refer to the set A from the statement of the induction principle. Generally, this set is the set of numbers for which the claim that we are trying to prove holds. In the first proof, it was the set of numbers n that are either even or odd. In the second proof, it was the set of numbers n for which $3^n$ is odd. Suppose we want to show that some claim holds for all positive integers. Here is a general template for proving this by induction:
(a) State the method of proof. For example, “The proof proceeds by induction.”
(b) Prove the “induction basis”. That is, prove that the number 1 satisfies the claim. (This step is often easy, but is crucially important, and should never be omitted!)
(c) Assume the “induction hypothesis”. That is, state the assumption that the claim holds for some positive integer k.
(d) Prove, using the induction hypothesis, that the claim holds for $k+1$. The proof should consist of a chain of clear statements, each logically following from the previous ones combined with our shared knowledge base. The final statement in the chain should state that the claim holds for $k + 1$.
(e) Conclude the proof. For example, “This completes the proof by induction.”
Theorem 2.1.3. For every positive integer n,
\[1 + 2 + \cdots + n = \frac{n(n + 1)}{2}.\]Proof. The proof proceeds by induction. For $n = 1$, we have $1 = \frac{1 \cdot 2}{2}$ and the claim holds. Assume $1 + 2 + \cdots + k = \frac{k(k + 1)}{2}$. Then
\[1 + 2 + \cdots + k + (k + 1) = \frac{k(k + 1)}{2} + (k + 1) = \frac{k(k + 1) + 2(k + 1)}{2} = \frac{(k + 1)(k + 2)}{2},\]which proves the claim for $k + 1$ and completes the proof by induction.
Sigma and Pi notations. Just as the $\bigcup$ symbol can be used to compactly express the union of many sets, the $\sum$ symbol can be used to express summations. For example,
\[1 + 2 + \cdots + n = \sum_{i=1}^n i = \sum_{1 \le i \le n} i = \sum_{i \in \{x : 1 \le x \le n\}} i.\]You should not assume just because $\sum$ appears that there is an actual summation, or that there are any summands at all. For example, when $n = 1$,
\[\sum_{i=1}^n i = 1,\]and when $n \le 0$,
\[\sum_{i=1}^n i = 0!\]Similarly, products can be expressed using the $\prod$ symbol, as in
\[2^0 \cdot 2^1 \cdot 2^2 \cdot \ldots \cdot 2^n = \prod_{i=0}^n 2^i.\]One thing to be aware of is that the empty product is defined to equal 1, so
\[\prod_{i=3}^1 i = \prod_{\substack{i \in \{2, 4, 10, 14\} \\ i \text{ is odd}}} i = 1.\]A single $\sum$ or $\prod$ symbol can also be used to describe the sum or product over more than one variable. For example,
\[\sum_{1 \le i, j \le n} (i + j) = \sum_{i=1}^n \sum_{j=1}^n (i + j).\]Suppose that a property $P$ holds for $n = 1$, and the following is true: If $P$ holds for all integers between 1 and $k$, then it also holds for $k + 1$. Under these assumptions, $P$ holds for all positive integers. This is the principle of strong induction. It differs from regular induction in that we can assume something stronger to derive the same conclusion. Namely, we can assume not only that $P$ holds for $k$, but that in fact $P$ holds for all positive integers up to $k$. We state the strong induction principle more formally, and then demonstrate its usefulness.
Strong Induction Principle: Given a set A of positive integers, suppose the following hold:
Then all positive integers belong to A.
Definition. An integer $p > 1$ is said to be prime if the only positive divisors of $p$ are 1 and $p$ itself.
Theorem 2.2.1. Every positive integer greater than 1 can be expressed as a product of primes.
Proof. The proof proceeds by strong induction. Since 2 is a prime, the claim holds for 2. (Note how the induction basis in this case is 2, not 1, since we are proving a claim concerning all integers equal to or greater than 2.) Now assume the claim holds for all integers between 2 and $k$. If $k+1$ is a prime then the claim trivially holds. Otherwise it has a positive divisor $a$ other than 1 and $k + 1$ itself. Thus, $k + 1 = ab$, with $2 \le a, b \le k$. Both $a$ and $b$ can be expressed as products of primes by the induction hypothesis. Their product can therefore also be thus expressed. This completes the proof by strong induction.
The versatility of induction. We have seen in the proof of Theorem 2.2.1 that if we want to prove a statement concerning all positive integers equal to or greater than 2, we can use induction (or strong induction) with 2 as the base case. This holds for any positive integer in the place of 2. In fact, induction is an extremely versatile technique. For example, if we want to prove a property of all even positive integers, we can use 2 as the base case, and then prove that if the property holds for $k$, it will also hold for $k + 2$. Generally we will just assume that such variations are ok, there is no need to state a separate induction principle for each of these cases.
Fairly subtle variations of induction are often used. For example, if we can prove that a statement holds for 1 and 2, and that if it holds for $k$ it will also hold for $k + 2$, we can safely conclude that the statement holds for all the positive integers. However, don’t get carried away with variations that are simply incorrect, like using 1 as a base case, proving that if a statement holds for $k$ then it also holds for $k + 2$, and then claiming its validity for all positive integers.
The following proof proceeds by contradiction. That is, we will assume that the claim we are trying to prove is wrong and reach a contradiction. If all the derivations along the way are correct, then the only thing that can be wrong is the assumption, which was that the claim we are trying to prove does not hold. This proves that the claim does hold.
Theorem 3.1.1. $\sqrt{2}$ is irrational.
Proof. We have seen previously that every integer is either even or odd. That is, for every $n \in \mathbb{Z}$ there exists $k \in \mathbb{Z}$, such that either $n = 2k$ or $n = 2k + 1$. Now, if $n = 2k$ then $n^2 = (2k)^2 = 4k^2 = 2 \cdot (2k^2)$, which means that if $n$ is even then $n^2$ is also even. On the other hand, if $n = 2k + 1$ then $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2 \cdot (2k^2 + 2k) + 1$, so if $n$ is odd then $n^2$ is also odd.
We now proceed with a proof by contradiction. Assume that $\sqrt{2}$ is rational, that is, $\sqrt{2} \in \mathbb{Q}$. (This is the assumption that should lead to a contradiction.) By definition, this means that there exist two numbers $p, q \in \mathbb{Z}$, with $q \neq 0$, such that
\[\frac{p}{q} = \sqrt{2},\]and thus
\[\left(\frac{p}{q}\right)^2 = 2.\]We can assume that $p$ and $q$ have no common divisor, since all common divisors can be divided out to begin with. We have
\[p^2 = 2q^2.\]This shows that $p^2$ is even, and consequently $p$ must be even; that is, $p = 2k$ for some $k \in \mathbb{Z}$. Then
\[(2k)^2 = 2q^2 \implies 4k^2 = 2q^2 \implies 2k^2 = q^2.\]This shows that $q^2$ is even, and consequently that $q$ is even. Thus both $p$ and $q$ are even, contradicting the fact that $p$ and $q$ have no common divisor. We have reached a contradiction, which completes the proof.
Proof Technique: Proof by contradiction. Suppose we want to prove some statement A by contradiction. A common template for such proofs is as follows:
(a) State the method of proof. For example, “The proof proceeds by contradiction.”
(b) State the assumption that should lead to the contradiction. For example, “Assume statement A does not hold.”
(c) Proceed with a chain of clear statements, each logically following from the previous ones combined with our shared knowledge base. The final statement in the chain should be a contradiction, either of itself (as in, $0 \neq 0$), or of some previous statement in the chain, or of part of our shared knowledge base.
(d) Conclude the proof. For example, “We have reached a contradiction, which completes the proof.”
Theorem 3.1.2. $\log_2 3$ is irrational.
Proof. The proof proceeds by contradiction. Assume that $\log_2 3$ is rational. By definition, there exist two numbers $p, q \in \mathbb{Z}$, with $q \neq 0$, such that
\[\log_2 3 = \frac{p}{q},\]which means that
\[2^{\frac{p}{q}} = 3,\]and thus
\[2^p = 3^q.\]We can assume that $p, q > 0$. (Indeed, if $\frac{p}{q} > 0$ then we can just work with $|p|$ and $|q|$, and if $\frac{p}{q} \leq 0$ we reach a contradiction of the form $3 = 2^{\frac{p}{q}} \leq 2^0 = 1$.) Now, any positive integer power of 2 is even, because it has 2 as a divisor, so $2^p$ is even. On the other hand, a positive integer power of 3 is odd, as we’ve seen previously. We have reached a contradiction.
We should not forget perhaps the most intuitive proof technique of all: the direct one. Direct proofs start out with our shared knowledge base and, by a sequence of logical derivations, reach the conclusion that needs to be proved. Such proofs are often particularly ingenious and surprising.
Consider the following well-known puzzle question. Take the usual $8 \times 8$ chessboard and cut out two diagonally opposite corner squares. Can the remaining 62 squares be tiled by domino-shaped $2 \times 1$ tiles, each covering two adjacent squares of the board? (That is, each tile can be placed either horizontally or vertically, so as to precisely cover two squares of the board.)
Theorem 3.2.1. A tiling as above is impossible.
Proof. Every tile covers one white square and one black square. Thus in any tiling as above, the number of white squares covered is the same as the number of black ones. The two removed squares have the same color, hence the number of white squares left on the board is not the same as the number of black ones. So the remaining squares cannot be tiled.
The above proof can also be phrased as a proof by contradiction, or even in terms of induction. However, even though such a phrasing might appear more formal, it is rather unnecessary, as the above proof is already logically sound (which is critical!), and better conveys the power (and dare I say, the beauty) of the argument.
Proof Technique: Direct proof. Here is a common template for direct proofs:
(a) Provide a chain of clear statements, each logically following from our shared knowledge base and the previous ones. The final statement in the chain should be the claim we need to prove.
(b) (Optional.) Conclude the proof. For example, “This completes the proof.”
For the next few lectures we will exercise our ability to prove mathematical statements, using the fertile ground of number theory. In the process we will learn new proof techniques and tricks of trade. The number-theoretic concepts and results we will cover will be useful throughout your computer science studies, and, indeed, throughout your involvement with mathematics.
The following result is commonly known as the division algorithm, even though it is not an algorithm at all.
Theorem 4.1.1. If $a$ and $b$ are integers and $b \neq 0$, then there is a unique pair of integers $q$ and $r$, such that $a = qb + r$ and $0 \leq r < |b|$.
Proof. We need to prove two things: that there is some such pair $q, r$ (existence) and that this pair is unique (uniqueness).
Let’s begin with existence. First we show that there is a pair $q, r \in \mathbb{Z}$ that satisfies $a = qb + r$ for some $r \geq 0$. This is easy after some playing around: Take $q = -\left\lfloor \frac{|a|}{b} \right\rfloor$ and $r = a + \left\lfloor \frac{|a|}{b} \right\rfloor b$. Since $|b| \geq 1$, it holds that $r \geq 0$. Now we need to show that such $q, r \in \mathbb{Z}$ exist with $r$ in addition being smaller than $|b|$. For this, consider the set $S$ of all $r \in \mathbb{N}$ that satisfy $a = qb + r$ for some $q \in \mathbb{Z}$. We’ve just shown that $S$ is nonempty, so it must have a smallest element, call it $r_0$. We have $a = q_0 b + r_0$. If $r_0 < |b|$ we’re done. Otherwise, we have $a = (q_0 b + |b|) + (r_0 - |b|)$, which means that $r_0 - |b|$ is a smaller element of $S$ than $r_0$, leading to a contradiction. This completes the existence proof.
| To prove uniqueness, suppose that $a = qb + r = sb + t$, with $0 \leq r, t < |b|$. Thus $(q - s)b + (r - t) = 0$. Since $0 \leq r, t < |b|$, we have $|r - t| < |b|$, hence $|(q - s)b | < | b|$ and $|q - s| < 1$. Since $q$ and $s$ are integers, this implies $q = s$. From this we have $r = t$ and the uniqueness proof is complete. |
Proof tip: When we need to prove that some mathematical object exists and is unique, it is useful to approach in two stages. First prove that at least one such object exists. This can be done either by directly constructing an object and demonstrating that it fulfills the requirements, or by assuming that no such object exists and reaching a contradiction. Then show that any two such objects must be the same.
The Well-Ordering Principle. In proving the division algorithm, we considered a certain set $S \subseteq \mathbb{N}$ and argued that since it is nonempty, it must have a smallest element. Why is this true? As with induction, we accept this proposition as an axiom. In general, the “well-ordering principle” states that any nonempty set of natural numbers must have a smallest element. As you will prove in the homework, the well-ordering principle is equivalent to the principles of induction and strong induction.
A more algorithmic view of Theorem 4.1.1 is as follows: If we divide the equation
\[a = qb + r\]by $b$ we get
\[\frac{a}{b} = q + \frac{r}{b}.\]Since $0 \leq r < |b|$, we get that if $b > 0$, then $0 \leq \frac{r}{b} < 1$ and thus $q = \left\lfloor \frac{a}{b} \right\rfloor$, the greatest integer less than or equal to $\frac{a}{b}$. If $b < 0$, then $0 \geq \frac{r}{b} > -1$ and thus $q = \left\lceil \frac{a}{b} \right\rceil$, the least integer greater or equal to $\frac{a}{b}$. This can be used to calculate $q$, from which we can derive $r$.
In Theorem 4.1.1, we call $q$ the quotient and $r$ the remainder. We use the notation $r = a \bmod b$ to denote that $r$ is the remainder when $a$ is divided by $b$. There is no need for a special notation for quotient, since we can just use $\left\lfloor \frac{a}{b} \right\rfloor$ and $\left\lceil \frac{a}{b} \right\rceil$, depending on the sign of $b$.
Definition: If $a$ and $b$ are such that $a \bmod b = 0$ we say that $a$ is a multiple of $b$, or that $b$ divides $a$ (or is a divisor of $a$). Note that this holds when there exists some integer $q$, such that $a = qb$. In particular, every integer divides 0, and every integer is a multiple of 1. When $b$ divides $a$ we write $b \mid a$, and when $b$ does not divide $a$ we write $b \nmid a$.
Definition: An integer $u$ is called a linear combination of a set of integers $a_1, a_2, \ldots, a_n$ if and only if there exist integer coefficients $c_1, $c_2, \ldots, c_n$ that satisfy
\[u = \sum_{i=1}^n c_i a_i.\]Theorem 4.2.1. Properties of divisibility:
(a) If $b \mid a$ and $c \mid b$ then $c \mid a$.
(b) If $b \mid a$ and $a \neq 0$ then $|b| \leq |a|$.
(c) If $b$ divides each of $a_1, a_2, \ldots, a_n$, then $b$ divides all linear combinations of $a_1, a_2, \ldots, a_n$.
(d) $a \mid b$ and $b \mid a$ if and only if $a = \pm b$.
Proof. We prove the properties in turn:
(a) Since $b \mid a$, there exists an integer $q$, such that $a = qb$. Similarly, there exists an integer $r$, such that $b = rc$. Thus $a = qb = qrc$. Since $qr$ is an integer, it holds that $c \mid a$.
(b) Since $b \mid a$, there exists an integer $q$, such that $a = qb$. This implies $|a| = |q| \cdot |b|$. Assume for the sake of contradiction that $a \neq 0$ but $|b| > |a|$. Then $|q| \cdot |b| < |b|$. Since $|b| > |a| > 0$, we can divide by $|b|$ to get $|q| < 1$, implying $q = 0$. Thus $a = qb = 0$, which is a contradiction.
(c) Consider a linear combination $u = \sum_{i=1}^n c_i a_i$. Since $b \mid a_i$, there exists an integer $q_i$, such that $a_i = q_i b$, for all $1 \leq i \leq n$. Thus
\[u = \sum_{i=1}^n c_i a_i = \sum_{i=1}^n c_i q_i b = b \cdot \sum_{i=1}^n c_i q_i.\]Since $\sum_{i=1}^n c_i q_i$ is an integer, we have $b \mid u$.
(d) For the “if” statement, note that if $a = \pm b$ then $b = qa$ and $a = qb$, for $q = \pm 1$, so $a \mid b$ and $b \mid a$. To prove the “only if” statement, assume that $a \mid b$ and $b \mid a$. This implies the existence of integers $q$ and $r$, such that $b = qa$ and $a = rb$. Thus $b = qrb$. If $b = 0$ then $a = 0$ and the claim that $a = \pm b$ holds. Otherwise we can divide by $b$ to get $qr = 1$. Note that in this case $q, r \neq 0$. Part (b) of the theorem implies that $|q| \leq 1$ and $|r| \leq 1$. Thus $q, r = \pm 1$ and the claim that $a = \pm b$ follows.
Proof tip: Often we need to prove that a proposition $A$ holds if and only if some other proposition $B$ holds. Such an “if and only if” (sometimes abbreviated as “iff”) statement is really composed of two implications, each of which needs to be proved. It is often useful to decouple these and prove them separately. First prove that “If $A$ then $B$,” and then prove that “If $B$ then $A$.” Another strategy is to prove that “If $A$ then $B$” and “If not $A$ then not $B$.”
If $d \mid a$ and $d \mid b$ then $d$ is a common divisor of $a$ and $b$. For example, 1 is a common divisor of any pair $a, b$. If $a$ and $b$ are not both 0 then, by Theorem 4.2.1(b), any common divisor of $a$ and $b$ is not greater than $\max(|a|, |b|)$. Thus the set of common divisors of $a$ and $b$ has a largest element, called the greatest common divisor of $a$ and $b$, or $\gcd(a, b)$. This is the integer $d$ that satisfies the following two criteria:
Note that when $a = b = 0$, there is no greatest common divisor, since any integer divides 0. When $a$ and $b$ are not both 0, we often want to compute $\gcd(a, b)$ efficiently. Note that the set of divisors of $a$ and $-a$ is the same, and similarly for $b$ and $-b$. Furthermore, if $a = 0$ then $\gcd(a, b) = b$, and if $a = b$ then $\gcd(a, b) = a = b$. Thus it suffices to concentrate on the case $a > b > 0$, without loss of generality.
Since $1 \leq \gcd(a, b) \leq b$, we can just test all integers between 1 and $b$ and choose the largest one that divides both $a$ and $b$. However, there is a much more efficient way to find greatest common divisors, called Euclid’s algorithm. This algorithm, one of the earliest in recorded history, is based on the following lemma.
Lemma 4.3.1. If $a = qb + r$ then $\gcd(a, b) = \gcd(b, r)$.
Proof. By Theorem 4.2.1(c), all common divisors of $b$ and $r$ also divide $a$, since $a$ is a linear combination of $b$ and $r$. Thus a common divisor of $b$ and $r$ is also a common divisor of $a$ and $b$. Similarly, since $r = a - qb$, a common divisor of $a$ and $b$ also divides $r$, so it is a common divisor of $b$ and $r$. Thus $a, b$ and $b, r$ have the same set of common divisors, and in particular the same greatest common divisor.
With this lemma in our toolbelt, Euclid’s algorithm is easy to describe. To find $\gcd(a, b)$, use the division algorithm (Theorem 4.1.1) to represent $a = qb + r$, where $0 \leq r < b$. (Remember that we are assuming that $a > b > 0$.) If $r = 0$ then $b \mid a$ and $\gcd(a, b) = b$. Otherwise $\gcd(a, b) = \gcd(b, r)$ and $b > r > 0$. We can thus repeat the above procedure recursively with the pair $b, r$. Every recursive call strictly reduces both numbers in the pair, so after at most $b$ steps the algorithm will terminate with a valid greatest common divisor of $a$ and $b$. You will formally prove the correctness of the algorithm in the homework.
We have seen that a common divisor of $a$ and $b$ divides any linear combination of $a$ and $b$. Now we will prove a surprising property known as Bezout’s identity that shows that the greatest common divisor of $a$ and $b$ is itself a linear combination of $a$ and $b$.
Theorem 4.4.1. For two integers $a$ and $b$ that are not both 0, $\gcd(a, b)$ is a linear combination of $a$ and $b$.
Proof.
As above, we can concentrate on the case $a > b > 0$. The proof proceeds by strong induction on the value of $a$. In the base case, $a = 2$, $b = 1$, and $\gcd(a, b) = 1 = 0 \cdot a + 1 \cdot b$.
Assume that the theorem holds for all pairs $a, b$ with $0 < b < a \leq k$. Consider a pair $a’, b’$ with $0 < b’ < a’ = k + 1$. If $b’ \mid a’$ then $\gcd(a’, b’) = b’$ and the theorem trivially holds. Otherwise use the division algorithm to express $a’ = qb’ + r$, where $0 < r < b’$. By the induction hypothesis, there exist coefficients $u$ and $v$, such that $\gcd(b’, r) = ub’ + vr$. Lemma 4.3.1 shows that $\gcd(a’, b’) = \gcd(b’, r)$, therefore $\gcd(a’, b’) = ub’ + vr = u b’ + v (a’ - qb’) = va’ + (u - vq)b’$.
This shows that $\gcd(a’, b’)$ is a linear combination of $a’$ and $b’$ and completes the proof by induction.
Bezout’s identity implies that the set of linear combinations of $a$ and $b$ is the same as the set of multiples of their greatest common divisor (!):
Corollary 4.4.2. An integer $z$ is a linear combination of $a$ and $b$ if and only if it is a multiple of $\gcd(a, b)$. In particular, $\gcd(a, b)$ is the least positive linear combination of $a$ and $b$.
Proof. By Theorem 4.2.1(c), since $\gcd(a, b)$ divides both $a$ and $b$, it divides any linear combination $z$ of $a$ and $b$, and thus $z$ is a multiple of $\gcd(a, b)$. On the other hand, we know by Bezout’s identity that there are coefficients $u$ and $v$, such that $\gcd(a, b) = ua + vb$, so if $z = c \cdot \gcd(a, b)$, then $z = c (ua + vb) = (cu)a + (cu)v$.
Definition: An integer $p > 1$ is said to be prime if its only positive divisors are 1 and $p$ itself. All other integers greater than 1 are called composite.
A composite number $n$ can be written as a product $n = ab$ of two strictly smaller numbers $1 < a, b < n$. Note that, by convention, 1 is neither prime nor composite. Here are all primes below 100:
\[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.\]Given a prime $p$ and another integer $a$, either $a$ is a multiple of $p$ or $\gcd(p, a) = 1$. Indeed, $\gcd(p, a)$ divides $p$, so it must be either 1 or $p$, and since $\gcd(p, a)$ also divides $a$ then either $\gcd(p, a) = 1$ or $a$ is a multiple of $p$. This can be used to prove a very important property of primes:
Theorem 5.1.1. Let $p$ be a prime.
(a) Given two integers $a$ and $b$, if $p \mid ab$ then either $p \mid a$ or $p \mid b$.
(b) Given $k$ integers $a_1, a_2, \ldots, a_k$, if $p \mid \prod_{i=1}^k a_i$ then $p \mid a_i$ for some $1 \leq i \leq k$.
Proof.
(a) If $p \mid a$ we are done. Otherwise $\gcd(p, a) = 1$ and by Bezout’s identity there exist linear coefficients $u$ and $v$ for which $1 = ua + vp$. Multiplying both sides by $b$ we get $b = uab + vpb$. Since $p$ divides $ab$, $p$ divides the whole sum $uab + vpb$. Therefore $p \mid b$.
(b) The proof proceeds by induction. The case $k = 1$ is trivial and $k = 2$ is handled in part (a). So we assume that the claim holds for some $k > 1$ and prove that it also holds for $k + 1$. Given that $p \mid \prod_{i=1}^{k+1} a_i$, we put $b = \prod_{i=1}^k a_i$. Since $p \mid ba_{k+1}$, part (a) implies that either $p \mid a_{k+1}$ or $p \mid b$. In both cases the claim holds, in the latter case by the induction hypothesis. This completes the proof by induction.
Theorem 5.1.1 can be used to derive a fundamental theorem of number theory. It is so fundamental it has “fundamental” in its name.
Theorem 5.1.2 (Fundamental Theorem of Arithmetic). Every positive integer can be represented in a unique way as a product of primes,
\[n = p_1 p_2 \cdots p_k \quad (p_1 \leq p_2 \leq \ldots \leq p_k).\]Proof. We first prove existence and then uniqueness. Actually, we already proved existence in one of the previous lectures as an illustration of strong induction, but give the proof here again for completeness. So, to prove that every integer can be represented as a product of primes we use strong induction. The base case $n = 1$ holds because the empty product, as we previously discussed, is defined to equal 1. The induction hypothesis assumes that for some $n > 1$, all positive integers $k < n$ can be represented as a product of primes. If $n$ is prime, then it is trivially a product of primes. Otherwise it can be written as $n = ab$, for $1 < a, b < n$. By the induction hypothesis, both $a$ and $b$ are products of primes, so their product $n$ is also a product of primes. This proves existence.
The proof that the above representation is unique proceeds by contradiction. Assume then that there exists some positive integer that can be represented as a product of primes in (at least) two ways. By the well-ordering principle, there is a smallest such integer $n$. It holds that
\[n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_l,\]where $p_1 \leq p_2 \leq \ldots \leq p_k$, $q_1 \leq q_2 \leq \ldots \leq q_l$, and $p_i \neq q_i$ for some $i$. By Theorem 5.1.1(b), since $p_i \mid q_1 q_2 \cdots q_l$, there must exist some $q_j$ for which $p_i \mid q_j$. Since $q_j$ is prime and $p_i > 1$, this can only occur when $p_i = q_j$. Thus we can eliminate $p_i$ and $q_j$ from the equation $p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_l$ and get two distinct representations of the positive integer number $n / p_i$ as a product of primes. This contradicts the assumption that $n$ is the smallest positive integer with this property, and concludes the proof of uniqueness.