Lemma 7.0. Let $n$ and $d \gt 0$ be arbitrary integers. For any integers $q$ and $r$ such that $n = d \cdot q + r$ and $0 \leq r \lt d$, $q$ and $r$ are unique.
Suppose that there exist integers $q_1, r_1, q_2, r_2$ such that $n = d \cdot q_1 + r_1$ and $n = d \cdot q_2 + r_2$ with $0 \leq r_1, r_2 \lt d$. Consider the following system of equations \begin{align*} n &= q_1 \cdot d + r_1 \\ n &= q_2 \cdot d + r_2. \end{align*} Subtracting gives us $0 = (q_1 - q_2) \cdot d + (r_1 - r_2)$. Rearranging this equation gives us $(q_2 - q_1) \cdot d = r_1 - r_2$. Since $(q_2 - q_1)$ is an integer, we have $d \mid (r_1 - r_2)$ by definition of divisibility. Since $-d \lt r_1 - r_2 \lt d$, we have $r_1 - r_2 = 0$ and therefore $r_1 = r_2$. Then from above, this gives us $(q_2 - q_1) \cdot d = 0$. Since $d \gt 0$, we have $q_2 - q_1 = 0$ and therefore $q_1 = q_2$. Thus, we have shown that $q$ and $r$ are unique. $$\tag*{$\Box$}$$
Definition 7.1. Let $n$ and $d \gt 0$ be integers. We define the functions $n \mathop{\mathbf{div}} d = q$ and $n \mathop{\mathbf{mod}} d = r$, where $q$ and $r$ are as defined by the Division Theorem.
These functions are defined as in the Rosen textbook and are standard definitions. We can think of $\mathbf{div}$ as the integer division operation in many programming languages that just returns the quotient and $\mathbf{mod}$ is the modulus operator. However, if we recall the painstaking work to define functions as a special kind of relation, these aren't really functions because they're undefined for $d = 0$. Unfortunately, this is the way it is.
Definition 7.2. The set of divisors of $n$ is defined by $\operatorname{Div}(n) = \{a : a \mid n\}$.
This is a nice definition because it is obvious what the common divisors of $m$ and $n$ are supposed to be: the intersection of $\operatorname{Div}(m)$ and $\operatorname{Div}(n)$.
Definition 7.3. If $m$ and $n$ are integers with $m \neq 0$ or $n \neq 0$, then the greatest common divisor of $m$ and $n$, denoted $\gcd(m,n)$, is the largest element of $\operatorname{Div}(m) \cap \operatorname{Div}(n)$.
From the way we've defined this, it's not entirely obvious that the gcd should exist. Without loss of generality, let $m \neq 0$. Then $\operatorname{Div}(m)$ has a largest element $m$ and a smallest element $-m$. This means that $\operatorname{Div}(m)$ is finite and that $\operatorname{Div}(m) \cap \operatorname{Div}(n)$ is also finite. Since 1 is a divisor for every integer, we know that $1 \in \operatorname{Div}(m) \cap \operatorname{Div}(n)$, which means that $\operatorname{Div}(m) \cap \operatorname{Div}(n)$ is non-empty. Since it's not empty, $\operatorname{Div}(m) \cap \operatorname{Div}(n)$ must contain a largest element, which is the gcd.
From the Division Theorem, we get the following result about the gcd by Étienne Bézout in the mid-1700s.
Theorem 7.4 (Bézout's Identity). For all integers $a$ and $b$ where $a$ or $b$ is nonzero, there exist integers $x$ and $y$ such that $\gcd(a,b) = a \cdot x + b \cdot y$.
Proof. Consider the set $S = \{ax + by \mid x,y \in \mathbb Z\}$. Note that it contains strictly positive (greater than zero) numbers, for instance $a^2+b^2$. Let $c = as + bt$ be the smallest strictly positive member of $S$.
We first have to show that $c$ is a common divisor of $a$ and $b$. Let's show $c \mid a$ first. Applying the Division Theorem, we have some $q$ and $0 \le r \lt c$ such that \begin{align*} a &= qc + r \Rightarrow \\ r &= a - qc \\ &= a - q(as + bt) \\ &= a(1-qs) - bqt \end{align*}
Therefore $r \in S$. Since $0 \le r \lt c$ and $c$ is the smallest strictly positive member of $S$, $r$ must be $0$. We've shown that $c \mid a$. The proof that $c \mid b$ follows similarly.
Now we need to show that $c$ is the greatest common divisor. Assume $d \mid a$ and $d \mid b$. Then $d \mid (as + bt)$ by Theorem 6.5 from last class. Since $d \mid c$ and $c$ is strictly positive, $d$ must be less than or equal to $c$. This completes the proof. $$\tag*{$\Box$}$$
Bézout's identity is interesting in that it provides a characterization for the gcd of $m$ and $n$. Suppose we have $m$, $n$, and what we think is $\gcd(m,n)$. Is there a way to check that the gcd is really correct without computing it? If we had the coefficients of Bézout's identity for $m$ and $n$, then we could check very easily. Of course, we're getting a bit ahead of ourselves, but keep this idea in mind while we tackle a more immediate question: how does one compute the gcd?
The obvious way to do this is to compute the set of divisors for $m$ and $n$, compute their intersection, and take the largest element in the intersection. The big problem with this approach is that factoring integers is a notoriously hard problem to solve efficiently. There are some heuristics that we can apply and some tricks that we can pull, but in general we do not have a fast algorithm for factoring numbers. This fact happens to be the backbone of many public-key cryptographic systems we use today.
However, if all we care about is the greatest common divisor and not any of the other divisors, then the following theorem will get us there efficiently.
Theorem 7.5. If $c = \gcd(a,b)$ and $b \neq 0$ then $c = \gcd(b, a \mathop{\mathbf{mod}} b)$.
Proof. Let $q = a \mathop{\mathbf{div}} b$ and $r = a \mathop{\mathbf{mod}} b$. It's easiest to just show that $\text{Div}(a) \cap \text{Div}(b) = \text{Div(a)} \cap \text{Div}(r)$. Our trusty Theorem 6.5 will be helpful again. Suppose that $x \mid a$ and $x \mid b$. Then $x \mid (a - qb) = r$. Conversely, if $y \mid b$ and $y \mid r$ then $y \mid (qb+r) = a$. Since the sets are the same, they share a greatest element. $$\tag*{$\Box$}$$
This result gives us a way to compute the gcd: $$\gcd(a,b) = \begin{cases} a & \text{if $b = 0$,} \\ \gcd(b, a \mathop{\mathbf{mod}} b) & \text{otherwise.} \end{cases}$$
This algorithm is called Euclid's algorithm, named after Euclid who describes it in the Elements. Euclid is the Greek mathematician from around 300 BC who, in the Elements, describes a lot of the elementary geometry, algebra, and number theory that we learn in school.
Example 7.6. Suppose we want to compute the gcd of 232 and 72. We apply Euclid's algorithm as follows: \begin{align*} \gcd(232,72) &= \gcd(72,16) \\ &= \gcd(16,8) \\ &= \gcd(8,0) \\ &= 8 \end{align*}
Example 7.7. Suppose we randomly pick the (rather too large) numbers 924 and 126 and want to compute their greatest common divisor. We apply Euclid's algorithm again: \begin{align*} \gcd(924, 126) &= \gcd(126,42) \\ &= \gcd(42,0) \\ &= 42 \end{align*} Which famously is The Answer to the Ultimate Question of Life, the Universe, and Everything. It was also, until recently, the only diophantine equation of the form $x = a^3 + b^3 + c^3$ for $x \lt 100$ yet to be solved.