Let's begin with some number theory. One of the first topics in elementary number theory is divsibility of integers. Division on integers is an interesting operation even though we've likely been dividing numbers since childhood without thinking about it too much. However, where it does come back to trip us up again is when we start to learn how to program. This usually comes in the form of trying to divide two numbers and then remembering that dividing two integers doesn't always give you an integer. This happens to be why division on integers is interesting.
Let $a,b$ be integers. We say that $a$ divides $b$, written $a \mid b$, if there exists an integer $n$ such that $a \cdot n = b$. We also say that $b$ is a multiple of $a$.
First, note that divisbility defines a relation in the sense that we defined last class. Of course, when we defined relations, we treated them as a set. Often times, we treat them as operators, writing them infix like $a \lt b$ or $a \mid b$ instead of treating them as sets and writing them $(a,b) \in \lt$ or $(a,b) \in \mid$.
Observe that by this definition, we have that for all integers $n$, $n \mid 0$ and in particular, $0 \mid 0$. At first this seems a bit odd because it feels like we are tempting fate by talking about dividing by 0, but if we take a more careful look at the definition of divisibility, we see that there actually isn't any division going on. What we're really talking about is multiplication. This important to keep in mind because Rosen, for whatever reason, chooses to add the condition that $a \neq 0$.
For all integers $a, b, c$, if $a \mid b$ and $a \mid c$, then $a \mid (b + c)$.
We can use what we've learned last week and translate it into logic-language: $$\forall a, b, c \in \mathbb Z, (a \mid b) \wedge (b \mid c) \rightarrow a \mid (b+c).$$ So in order to prove this statement is true, we need to consider every integer for $a,b,c$ and assume that our hypothesis, $a \mid b$ and $a \mid c$, is true. Remember that since this is an implication, we don't care about the case when we don't have $a,b,c$ such that $a \mid b$ and $a \mid c$.
Let $a,b,c$ be arbitrary integers and assume that $a \mid b$ and $a \mid c$. Since $a \mid b$, there exists an integer $m$ such that $b = m \cdot a$, and since $a \mid c$, there exists an integer $n$ such that $c = n \cdot a$. Now, consider the integer $b + c$. We have $$b + c = a \cdot m + a \cdot n = a \cdot (m + n).$$ Since $m + n$ is an integer, by definition of divisibility we have $a \mid (b+c)$.
Let's review what it is that we've done in this proof.
| Let $a,b,c$ be arbitrary integers | Since our claim about $a,b,c$ must hold for all possible integers, we simply say that they're arbitrarily chosen. We can think of $a,b,c$ as placeholders for any integers that satisfy our condition. |
| and assume that $a \mid b$ and $a \mid c$. | Here is our condition under which we chose $a,b,c$ and the assumption that we need to make to prove the theorem. |
| Since $a \mid b$, there exists an integer $m$ such that $b = m \cdot a$, | This is the definition of divsibility. Just like above, we don't know exactly which integer works, we only know that one of them works, so we give it a name (in this case $m$). |
| and since $a \mid c$, there exists an integer $n$ such that $c = n \cdot a$. | This is the definition of divsibility again. Here, we make sure to choose a different variable name that hasn't been used ($n$). |
| Now, consider the integer $b + c$. | This is because adding two integers gives us another integer. |
| We have $$b + c = a \cdot m + a \cdot n = a \cdot (m + n).$$ | This is some simple algebraic manipulation. |
| Since $m + n$ is an integer, by definition of divisibility we have $a \mid (b+c)$. | This follows from the above algebra, and we apply the definition of divisibility. |
| $$\tag*{$\Box$}$$ | We end proofs with a box. In typography, this is called a tombstone and you often see these in publications like magazines. In mathematics, some call this a halmos, after Paul Halmos, who first used it in the mathematical context. |
Here is another simple theorem about divisibility.
For all integers $a, b, c$, if $a \mid b$, then $a \mid bc$.
Let $a,b,c$ be arbitrary integers and assume that $a \mid b$. Since $a \mid b$, there exists an integer $n$ such that $a \cdot n = b$. Now, consider the integer $b \cdot c$. We have $$b \cdot c = (a \cdot n) \cdot c = a \cdot (n \cdot c).$$ Since $n \cdot c$ is an integer, by definition of divisibility, we have $a \mid bc$.
A binary relation $R$ is transitive if $\forall a, b, c$, $a \mathrel R b \wedge b \mathrel R c \rightarrow a \mathrel R c$.
In other words, if I know that $a$ is related to $b$ in some way and $b$ is related to $c$, then I can conclude that $a$ is related to $c$. The subset relation is a transitive relation that we've seen already: if we know that $A \subseteq B$ and $B \subseteq C$, it's not too hard to argue that $A \subseteq C$. Similarly, implication is also transitive: if $p \rightarrow q$ and $q \rightarrow r$, then it's not too hard to see that $p \rightarrow r$. We will show that divsibility is transitive.
For all integers $a, b, c$, if $a \mid b$ and $b \mid c$, then $a \mid c$.
Let $a, b, c$ be arbitrary integers and assume that $a \mid b$ and $b \mid c$. Since $a \mid b$, there exists an integer $m$ such that $b = m \cdot a$. Since $b \mid c$, there exists an integer $n$ such that $c = n \cdot b$. Then we get $$c = n \cdot b = n \cdot (m \cdot a) = (n \cdot m) \cdot a.$$ But $n \cdot m$ is also an integer, so by the definition of divisibility, we have $a \mid c$.
We can use the facts that we've shown so far to prove the following theorem, which will be left as an exercise.
For all integers $a,b,c,m,n$, if $a \mid b$ and $a \mid c$, then $a \mid (bm + cn)$.
Now, we'll take a trip back to grade school and think about division again. Recall that if we divide two numbers $a$ by $b$, if $a$ is a multiple of $b$ (if $b \mid a$), we get an integer $q$ which we call the quotient. But if $a$ isn't a multiple of $b$, we get a remainder $r$. The following theorem, called the Division Theorem formally states that whenever we divide two numbers $a$ and $b$, we will always be able to "get" the integers $q$ and $r$ (they exist) and that they're unique.
For all integers $n$ and $d \gt 0$, there exist unique integers $q$ and $r$ such that $n = d \cdot q + r$ and $0 \leq r \lt d$.
To prove this theorem, we have to show two things:
Let's prove existence first as a lemma. This will be an example of a non-constructive existence proof. That is, we'll be showing that an appropriate $q$ and $r$ have to exist, but we don't actually give a way to find them. This is typical of existence proofs that rely on contradiction: we assume that the element we want can't exist and then run into a contradiction and conclude that the element must exist after all.
For all integers $n$ and $d \gt 0$, there exist integers $q$ and $r$ such that $n = d \cdot q + r$ and $0 \leq r \lt d$.
Let $n$ and $d \gt 0$ be arbitrary integers. Consider the set $S = \{n - d \cdot q \mid q \in \mathbb Z\}$. Since $d \gt 0$ and $q \in \mathbb Z$, there must be some non-negative element in $S$. Let $r$ be the smallest non-negative member of $S$ and let $q$ be such that $r = n - d \cdot q$. We want to show that $r \lt d$.
Suppose that it isn't and we have $r \geq d$. Then we have $0 \leq r-d \lt r$, and $r-d$ is also a non-negative element of $S$. However, this means that there is a smaller element of $S$ than $r$, which contradicts our assumption that $r$ was the smallest non-negative element of $S$. Therefore, it can't be the case that $r \geq d$.
Since $q \in \mathbb Z$ is such that $r \in S$, we have that $r = n - d \cdot q$. This gives us $n = d \cdot q + r$ with $0 \leq r \lt d$ as desired.
So now that we know that our desired integers have to be out there somewhere, we need to show that they're the only ones. To see how we might do this, it's worth considering the definition of a bespoke quantifier, $\exists!$. This is called the unique existential quantifier and it's not really necessary, because we can express the definition of unique existence without it: \[\exists x \in S, (P(x) \wedge (\forall y \in S, P(y) \rightarrow x = y)).\]
This says that there exists an element $x \in S$ such that $P(x)$ holds and if $P(y)$ holds for any $y \in S$, it must be the case that $x = y$. In other words, the only element for which $P$ can hold is $x$.
This second part of the statement gives us an idea of how to prove that our integers are unique: we assume that we have two solutions, and then arrive at the conclusion that these two solutions were the same to begin with.
Let $n$ and $d \gt 0$ be arbitrary integers. By Lemma 3.8, there exist integers $q$ and $r$ such that $n = d \cdot q + r$ and $0 \leq r \lt d$. We want to show that $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$. Without loss of generality, let $r_1 \geq r_2$ and 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 $0 \leq 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.
First, some more terminology.
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 (3.7).
In other words, $\mathbf{mod}$ gives us the quotient when we try to divide $n$ by $d$ and $\mathbf{mod}$ gives us the remainder. We can think of $\mathbf{div}$ as the integer division operation in many programming languages that just returns the quotient (i.e. n // d in Python) and $\mathbf{mod}$ is the modulus operator (i.e. n % d). In our case, it is just a convenience to avoid having to say "$q$ and $r$ as in the Division Theorem" over and over.
In the Division Theorem, the integer $d$ is named such because it is called the divisor.
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)$.
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.
For all integers $m$ and $n$, there exist integers $a$ and $b$ such that $\gcd(m,n) = a \cdot m + b \cdot n$.
If $m = n = 0$, then any $a$ and $b$ works. So without loss of generality, we have non-zero $m$ or $n$. Consider a set $S = \{am + bn \mid a,b \in \mathbb Z\}$. Let $d$ be the least positive integer in $S$ and let $a$ and $b$ be such that $d \in S$. First, we will show that $d$ is a common divisor of $m$ and $n$.
Suppose otherwise that $t$ isn't a common divisor of $m$ and $n$. Without loss of generality, say $d \not \mid m$. Then by the Division Theorem, there exist $q$ and $r$ such that $m = q \cdot d + r$ and $d \gt r \neq 0$. Then we have \begin{align*} r &= m - q \cdot d \\ &= m - q \cdot (am + bn) \\ &= (1-qa)m + (-bq)n \end{align*} This gives us $r \in S$. But since $r \lt d$, this contradicts $d = \min S$. Therefore, $d$ must be a common divisor of $m$ and $n$.
Now, consider any common divisor $c$ of $m$ and $n$. Then there exist integers $s$ and $t$ such that $m = cs$ and $n = ct$. This gives us \begin{align*} d &= am + bn \\ &= acs + bct \\ &= c \cdot (as + bt) \end{align*} Therefore, $c \mid d$ and therefore $c \leq d$. Thus, $d = \gcd(m,n)$.
Bézout's lemma is also called Bézout's identity. Confusingly, Bézout has another famous result named after him in algebraic geometry called Bézout's theorem.
Bézout's lemma 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 lemma 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.
If $d = \gcd(a,b)$, $b \neq 0$, and $r = a \mathop{\mathbf{mod}} b$, then $d = \gcd(b,r)$.
Let $a$ and $b \gt 0$ be arbitrary. Let $q$ be such that $a = qb + r$. If $d \mid a$ and $d \mid qb$, then $d \mid (a - qb)$, and therefore, $d \mid r$. In other words, $d$ is a common divisor of $b$ and $r$. Now consider an arbitrary common divisor $c$ of $b$ and $r$. If $c \mid b$ and $c \mid r$, we have $c \mid (qb+r) = a$, so $c$ is also a common divisor for $a$. This means we must have $c \leq d$. Therefore, $\gcd(b,r) = d = \gcd(a,b)$.
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}$$
which becomes the following function fairly straightforwardly:
def euclid(a,b):
if b == 0:
return a
else:
return euclid(b, a%b)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.
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*}