Lecture 3: Divisibility

\( \newcommand{\set}[1]{\{#1\}} \newcommand{\comprehension}[2]{\{#1\,:\,#2\}} \newcommand{\size}[1]{\vert#1\vert} \newcommand{\true}{\top} \newcommand{\false}{\bot} \newcommand{\limplies}{\rightarrow} \newcommand{\divides}{\mathbin{\vert}} \newcommand{\mult}{\mathbin{\cdot}} \newcommand{\xor}{\oplus} \newcommand{\union}{\cup} \newcommand{\intersect}{\cap} \newcommand{\complement}[1]{\overline#1} \newcommand{\powerset}{\mathcal{P}} \newcommand{\ixUnion}{\bigcup} \newcommand{\ixIntersect}{\bigcap} \newcommand{\Div}{\mathrm{Div}} \newcommand{\gcd}{\mathrm{gcd}} \newcommand{\divmod}{\mathop{\mathbf{divmod}}} \newcommand{\div}{\mathop{\mathbf{div}}} \newcommand{\mod}{\mathop{\mathbf{mod}}} \newcommand{\defeq}{\stackrel{\text{def}}{=}} \)

For this discussion, the default domain of discourse will be $\mathbb{Z}$, the integers. Note that we are drawing from Chapter 4 of Professor Babai's Discrete Mathematics Lecture Notes (PDF), adapting some material from Rosen.

Definition 3.1 We define $a$ divides $b$ (in notation $a \divides b$) via

\begin{equation*} a \divides b \iff \exists d,\, a \mult d = b \end{equation*}

In this case, we will say “$a$ divides $b$,” “$a$ is a divisor of $b$,” or “$b$ is a multiple of $a$.”

Note that in addition to the usual (expected) divisibilies, we have $\forall n, n \divides 0$, because $\forall n, n \cdot 0 = 0$, and this includes $0 \divides 0$. This is a bit surprising, but note that “divisibility” is defined in via multiplication, not division. Rosen restricts the notion of divisibility so that $a \not= 0$. Following Babai, we do not make that restriction.

Theorem 3.2 $\forall a \, b_1 \, b_2,\, a \divides b_1 \land a \divides b_2 \limplies a \divides b_1 + b_2$.

Proof This somewhat complicated looking theorem can be expressed in ordinary mathematical English concisely: the multiples of an integer are closed under addition. To prove this, the first thing we do is get rid of that scary looking quantification block, by pronouncing the incantation, “Let $a$, $b_1$, and $b_2$, be fixed by arbitrary.” The “arbitrary” part of this is that we're making no assumptions about the names we're introducing, they're just names. The “fixed” part means that we're going to assume that $a$, $b_1$, and $b_2$ stand for specific values, which we'll refer to by these names.

Next, we break the resulting implication into two hypotheses, $a \divides b_1$ and $a \divides b_2$ that we may assume, and a conclusion $a \divides b_1 + b_2$ that we have to prove from those assumptions. To use the divisibility hypotheses, we unfold the definitions to $\exists d,\, a \cdot d = b_1$ and $\exists d, a \cdot d = b_2$. Don't be confused: although we're reusing $d$, they have separate bindings. Now, to use an existential hypotheses, we can introduce a new variable that witnesses the existential, thus, “Let $n_1$ and $n_2$ be such that $a \cdot n_1 = b_1$, and $a \cdot n_2 = b_2$.” If this seems suspiciously like how we handled universal quantifiers in the previous paragraph, let me point out a salient difference: we introduce a new variable to eliminate an outer universal quantifier in the conclusion we're trying to prove, and we introduce a new variable to eliminate an outer existential quantifier in a hypothesis. With these choices of $n_1$ and $n_2$, we do a little simple algebra:

\begin{align*} a \cdot n_1 + a \cdot n_2 &= b_1 + b_2\\ a \cdot (n_1 + n_2) &= b_1 + b_2 \end{align*}

We can now introduce an existential quantifier, replacing the witnessing term $n_1+n_2$ with an existentially quantified variable $d$ (which need not be new, so long as there are no old occurrences that will be captured by the newly introduced quantifier), to get $\exists d,\, a \cdot d = b_1 + b_2$, and then finally fold the definition of divisibility, resulting in $a \divides b_1 + b_2$ as required.

$\Box$ Theorem 3.2

Theorem 3.3 $\forall a \, b \, c,\, a \divides b \limplies a \divides c \cdot b$.

Proof Again, we can state this concisely: the multiples of a given number are closed under integer multiplication. We'll give a proof without all of the meta-discussion this time.

Let $a$, $b$, and $c$ be fixed but arbitrary. We assume $a \divides b$, and must show $a \divides c \cdot b$. Let $n$ witness $a \divides b$, i.e., $a \cdot n = b$. We now do a little algebra:

\begin{align*} c \cdot a \cdot n &= c \cdot b\\ a \cdot (c \cdot n) &= c \cdot b\\ \end{align*}

Thus, $c \cdot n$ witnesses that $a \divides c \cdot b$, as required.

$\Box$ Theorem 3.3

By the way, we use a $\Box$ to note the end of a proof. Some mathematics texts use “QED" for the same purpose, “QED” abbreviating “quod erat demonstrandum,” which is Latin for “that which was to be demonstrated.” If you want, you can use “QED,” but I'll stick with $\Box$.

Corollary 3.4 $\forall a \, b_1 \, b_2 \, c_1 \, c_2,\, a \divides b_1 \land a \divides b_2 \limplies a \divides c_1 \cdot b_1 + c_2 \cdot b_2$.

*Exercise 3.5 Prove Corollary 3.4. Note that it should not be necessary to unfold and fold the definition of divisibility. Try to give a concise, English language statement of the statement of the corollary.

Definition 3.6 We say that a binary relation $R$ is transitive if $\forall a \, b \, c,\, a \mathrel{R} b \land b \mathrel{R} c \limplies a \mathrel{R} c$.

Many familiar mathematical relations ($=$, $\lt$, $\leq$) are transitive.

Theorem 3.7 Divisibility is transitive, i.e., $\forall a \, b \, c,\, a \divides b \land b \divides c \limplies a \divides c$.

Proof of Theorem 3.7 Let $n_1$ be such that $a \cdot n_1 = b$, and $n_2$ be such that $b \cdot n_2 = c$. We can now see that

\begin{equation*} a \cdot (n_1 \cdot n_2) = (a \cdot n_1) \cdot n_2 = b \cdot n_2 = c, \end{equation*}

whence $n_1 \cdot n_2$ witnesses $a \divides c$.

$\Box$ Theorem 3.7

Definition 3.8 The set of divisors of $n$ is $\Div(n) = \comprehension{a}{a \divides n}$.

For example $\Div(6) = \set{\pm 1, \pm 2, \pm 3, \pm 6}$. If the $\pm$ comes as a surprise, remember, our default domain of discourse for this lecture is $\mathbb{Z}$, not $\mathbb{N}$; while $\Div(0) = \mathbb{Z}$.

Theorem 3.9 $\forall a \, b,\, a \divides b \limplies \Div(a) \subseteq \Div(b)$.

Exercise 3.10 Prove Theorem 3.9.

Definition 3.11 If $m$ and $n$ integers, not both zero, then the greatest common divisor of $m$ and $n$ is the largest element of $\Div(m) \intersect \Div(n)$.

This definition begs for a proof of well-definedness on the domain $\comprehension{(m,n) \in \mathbb{Z} \times \mathbb{Z}}{m \not= 0 \lor n \not= 0}$. Let's give it.

If we just blunder forward, this proof is going to have two nearly identical cases, one in which $m \not= 0$, and one in which $n \not= 0$. As we've made no other assumptions about $m$ or $n$, those subproofs will be identical up to interchanging the names. Rather than repeating ourselves, we'll say, "Without loss of generality, assume $m \not= 0$,” or even (on the board) “WLOG $m\not=0$.”

If $m\not=0$, the elements of $\Div(m)$ are bounded above and below by $\pm m$, so $\Div(m)$ is finite, and so $\Div(m) \intersect \Div(n) \subseteq \Div(m)$ is finite. Also, it's clear that $\forall q, 1 \in \Div(q)$ is witnessed by $q$ itself, so $\Div(m) \intersect \Div(n)$ is non-empty. It follows from the latter that $\Div(m) \intersect \Div(n)$ has an element, and from the former that if it has one, it must have a largest one.

Theorem 3.12 (The Division Theorem) $\forall n \, d,\, d>0 \limplies \exists! q \, r,\, 0 \leq r \lt d \land n = d \cdot q + r$.

There's a fair bit going on here, beginning with that $!$ after the $\exists$. This is used to indicated that not only do there exist $q$ and $r$ that satisfy the quantified formula, but that they are unique. Recalling that we can define a function when we have existence (i.e., totality) and uniqueness (i.e., single-valuedness), it's easy to see why such claims are both important and common.

Of course, we can't just whip up new logical syntax on a whim. Fortunately, we can define this syntax, and understand it as a convenient abbreviation:

\begin{equation*} \exists! x, \, \varphi(x) \defeq \exists x,\, \varphi(x) \land \forall y,\, \varphi(y) \limplies x = y. \end{equation*}

We'll give two quite different proofs of existence. The first will be a non-constructive proof, terce and elegant; the second will be a constructive proof that provides additional insight.

Proof (existence, non-constructive). Let $n$ and $d>0$ be fixed but arbitrary. Consider the set $A = \comprehension{n - d \cdot q}{q \in \mathbb{Z}}$. It is easy to see (because $d\not=0$, and $q$ can be positive or negative), that $A$ must have a non-negative member, and therefore a least non-negative member $r$. Fix $q$ such that $r = n - d \cdot q$. We claim that $r \lt d$, otherwise $0 \leq r-d \lt r$ is a non-negative element element of $A$, contracting the minimality of $r$. Now, let $q\in \mathbb{Z}$ witness that $r\in A$. We have $r = n - d \cdot q$, which we can rearrange to $n = d \cdot q + r$, as required.

Proof (existence, constructive). We begin by considering the Division Theorem over $\mathbb{N}$, and define a function $\divmod : \mathbb{N} \times \mathbb{N} \to \mathbb{N} \times \mathbb{N}$ by induction on the first argument $n$ as follows. Note that our syntactic convention will be that $\divmod$ is an infix operator of precedence lower than any arithmetic operation.

\begin{align*} 0\divmod d &= (0,0)\\ n+1 \divmod d &= \begin{cases} (q',r'+1), &\text{if $r'+1 \not= d$, where $(q',r') = n \divmod d$}\\ (q'+1,0), &\text{otherwise} \end{cases} \end{align*}

We can easily see, by induction on $n$, that if $n \divmod d = (q,r)$, then $n = q \cdot d + r$, and moreover, that if $d \not=0$, then $r \lt d$. Ordinarily, we'd leave things there, but rather than being glib about it, let's use this as an opportunity to sort out proofs by induction over $\mathbb{N}$.

To prove a universal statement $\forall n,\, \varphi(n)$ over $\mathbb{N}$, it suffices to prove $\varphi(0)$, which is called the basis of the induction, and also to prove $\forall n,\, \varphi(n) \limplies \varphi(n+1)$, which is called the induction step of the proof. To understand why this works, consider $C_{\varphi} = \comprehension{n\in\mathbb{N}}{\lnot \varphi(n)}$, the set of counter-examples to the theorem we want to prove. If this set is empty, i.e., there are no counter-examples, then the universal theorem must be true (recall $\forall \equiv \lnot \exists \lnot$). But if the set is non-empty, there must exist a least counter-example $n$. That least counter-example must either be $0$, or it must be $n'+1$ for some $n'$ which is not a counter-example. The basis case of the induction rules out $0$ as being the least counter-example, and the induction case rules out a successor as being the least counterexample. So, we have,

Lemma 3.13 $\forall n\,d,\, n \divmod d = (q,r) \limplies n = q \cdot d + r \land d \not=0 \limplies r \le d$.

Note that we don't have to worry about $0 \leq r$, as we're in $\mathbb{N}$, where this is true for all $r$.

Proof, By induction on $n$.

Basis Case. We have to show, for all $d$, that $0 \divmod d = (q,r) \limplies 0 = q \cdot d + r$, and that if $d \gt 0$, then $r \le d$. For the first part, let $d$ be fixed but arbitrary. By definition of $\divmod$, $0 \divmod d = (0,0)$, and we can easily see that $0 = 0 \cdot d + 0$ as required. For the second part, if $d\gt 0$ is fixed by arbitrary, we can immediately conclude that $d \gt 0 = r$ as required.

Induction Case. For the first part, we get to assume that if $d$ is fixed but arbitrary, and $n' \divmod d = (q',r')$, that $n' = q' \cdot d + r'$. We have to show that if $n = n'+1$, and $n \divmod d = (q,r)$, then $n = q \cdot d + r$. To that end, there are two cases in the definition of $n \divmod d$ based on the definition of $n' \divmod d$. If $r' + 1 \not= d$, then $(q,r) = (q',r'+1)$, and we can reason as follows:

\begin{align*} q \cdot d + r &= q' \cdot d + r' + 1 \\ &= n' + 1\\ &= n \end{align*}

as required. In the second case, $r' + 1 = d$, in which case $(q,r) = (q'+1,0)$, and we can reason as follows:

\begin{align*} q \cdot d + r &= (q' + 1) \cdot d + 0 \\ &= q' \cdot d + d \\ &= q' \cdot d + r' + 1\\ &= n' + 1\\ &= n \end{align*}

as required.

For the second part, assume that $n = n'+1$, $(q',r') = n' \divmod d$, $d \gt 0$ and $r' \lt d$. Let $(q,r) = n \divmod d$. As above, there are two cases, depending on whether $r'+1 = d$. If $r'+1 = d$, then $r = 0$, and $0 \lt d$ by hypothesis. If $r'+1 \lt d$, then $r = r'+1$, and so $r \lt d$ as required.

It's worth noting, that our definitions imply $n \divmod 0 = (0,n)$ for all $n\in\mathbb{N}$, which might be surprising, but which still preserved $n = q \cdot d + r$.

Having defined $\divmod : \mathbb{N} \times \mathbb{N} \to \mathbb{N} \times \mathbb{N}$, we now want to extend it to $\divmod : \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z} \times \mathbb{Z}$. Let's consider the first argument $n$, first. If $n \in \mathbb{Z} - \mathbb{N}$, i.e., $n$ is negative, then $-n \in \mathbb{N}$, and so if $(q',r') = -n \divmod d$, then $-n = q \cdot d + r$. By elementary algebra, $n = (-q') \cdot d + (-r)$. If $r = 0$, so that $-r = 0$, we have $n = (-q') \cdot n + 0$, and can define $(q,r) = (q',0)$. If $r \not= 0$, then $d+r$ is a positive number less than $d$, and we can compute:

\begin{align*} n &= (-q') * d - r'\\ &= (-q') * d - d + d - r'\\ &= (-q'-1) * d + (d'-r) \end{align*}

and so define $n \divmod d = (q,r) = (-q'-1,d-r)$.

Although there's nothing about the theorem that requires us to do so, we can extend the domain of $\divmod$ to $d \lt 0$ in much the same way, resulting in a total function. Mathematicians will often say “mutatis mutandis,” a Latin phrase meaning, “changing what needs to be changed,” and leave it at that. Mutatis mutandis.

Proof (uniqueness). Suppose we have $n$ and $d\gt 0$, along with $q_1$, $q_2$, $r_1$, and $r_2$ such that $n = q_i \cdot d + r_i$, and $0 \lt r_i \lt d$ for $i \in \set{1,2}$. We need to show $q_1 = q_2$ and $r_1 = r_2$. Without loss of generality, $r_1 \geq r_2$. We can now do a bit of algebra:

\begin{align*} n &= q_1 \cdot d + r_1\\ n &= q_2 \cdot d + r_2\\ \end{align*}

subtracting both sides yields

\begin{align*} 0 &= (q_1 - q_2) \cdot d + (r_1 - r_2) \end{align*}

We can easily see that $d \divides 0$ and $d \divides (q_1 - q_2) \cdot d$, whence $d \divides r_1 - r_2$. Since $0 \leq r_1 - r_2 \lt d$, it must be the case that $r_1 - r_2 = 0$, i.e., $r_1 = r_2$. From this, and the equation above, we have $(q_1 - q_2) \cdot d = 0$. Since $d\gt 0$, we must have $q_1 - q_2 = 0$, i.e., $q_1 = q_2$, as required.

$\Box$ Theorem 3.12

Definition 3.14 If $n$ and $d>0$ are integers, define $n \div d = q$ and $n \mod d = r$, as the $q$ and $r$ whose existence and uniqueness is guaranteed by the Division Theorem.

There's something just a bit off about the definition we just gave, as $\div$ and $\mod$ aren't total, so if we're being really picky about things, we're defining partial, single-valued relations on $(\mathbb{Z} \times \mathbb{Z}) \times \mathbb{Z}$, and we're abusing both function notation and the equality symbol here. This is a traditional abuse, and we'll need to live with it if we want other folks to understand what we're doing. We just need to rule out the possibility that $d=0$, as we traditionally do.

Of course, we could finesse the issues of totality and single-valuedness, by defining $\div$ and $\mod$ in terms of $\divmod$, which is sensible, but non-standard.

Our non-constructive proof of the division theorem sets us up for a particularly pretty, and surprising, result:

Theorem 3.15 Suppose $d = \gcd(m,n)$. Then there exist $a$ and $b$ such that $d = a \cdot m + b \cdot n$.

Proof If $m$ and $n$ are both $0$, the result is trivial: any $a$ and $b$ will do! So without loss of generality, assume that at least one of $m$ and $n$ is non-zero. As in the non-constructive proof of the division theorem, let $d'$ be the least positive element of the set $A = \comprehension{a \cdot m + b \cdot n}{a,\, b \in \mathbb{Z}}$, and let $a$ and $b$ be witnesses that $d'\in A$. Since $d \divides m$ and $d \divides n$, we must have $d \divides a \cdot m + b \cdot n$, and so $d \divides d'$. It suffices to show that $d'$ is a common divisor of $m$ and $n$. Without loss of generality, we consider $m$. If $d'$ does not divide $m$, we know there exists $q$ and $r$ such that $m = q \cdot d' + r$, and $d' \gt r \not= 0$. But now,

\begin{align*} r &= m - q \cdot d' \\ &= m - q \cdot (a \cdot m + b \cdot n)\\ &= (1 - q \cdot a) \cdot m + (-b) \cdot n, \end{align*}

contradicting our choice of $d'$ as the least positive linear combination of $m$ and $n$.

$\Box$ Theorem 3.15

Euclid's Algorithm

We start with a simple observation:

Theorem 3.16 If $d = \gcd(a,b)$, $b \not= 0$, and $r = a \mod b$, then $d = \gcd(b,r)$.

Proof Let $a$ and $b>0$ be fixed but arbitrary. Let $q$ be $a \div b$, so that $a = q \cdot b + r$. If $d \divides a$ and $q \cdot b$, then $d \divides a - q \cdot b$, so $d \divides r$. On the other hand, if $d \divides b$ and $d \divides r$, we must have $d \divides a = q \cdot b + r$. Thus, $\Div(a) \intersect \Div(b) = \Div(b) \intersect \Div(r)$, and the result follows.

$\Box$ Theorem 3.16

We can use Theorem 3.16 to compute gcd's very efficiently, without the need to factor a number, or compute divisors, via:

\begin{equation*} \gcd(a,b) = \begin{cases} a, &\text{if $b = 0$}\\ \gcd(b,a \mod b),&\text{otherwise}\\ \end{cases} \end{equation*}

For example,

\begin{align*} \gcd(15,9) &= \gcd(9,6)\\ &= \gcd(6,3)\\ &= \gcd(3,0)\\ &= 3 \end{align*}

This is called “Euclid's Algorithm.” Euclid's algorithm gives us an alternative, constructive proof of Theorem 3.15, by “instrumenting” the gcd calculation above. For example, to compute the gcd of $x = 152$ and $y = 124$, we compute successive values of $a_i$, $b_i$, $ax_i$, $ay_i$, $bx_i$, and $by_i$ such that,

by first setting

and then producing successive values by computing $(q,r) = a_i \divmod b_i$, solving

\begin{align*} r &= a_i - q \cdot b_i\\ &= (ax_i \cdot x + ay_i \cdot y) - (q \cdot bx_i \cdot x + by_i \cdot y)\\ &= (ax_i - q \cdot bx_i) \cdot x + (ay_i - q \cdot by_i) \cdot y\\ \end{align*}

This enables us to update as follows:

We can easily organize such a calculation as a table:

a ax ay b bx by
152 1 0 124 0 1
124 0 1 28 1 -1
28 1 -1 12 -4 5
12 -4 5 4 9 -11
4 9 -11 0 -31 38

From which we can infer $4 = 9 \cdot 152 - 11 \cdot 124$, which I invite you to check.

*Exercise 3.17 Compute $m$ and $n$ such that $\gcd(935,578) = m * 935 + n * 578$.

Exercise 3.18 If you know how to program, write a function euclid in your favorite language that takes two natural numbers $a$ and $b$, and returns a triple $(d,m,n)$ such that $d$ is the greatest common divisor of $a$ and $b$, and $d = a \cdot m + b \cdot n$. Use your program to check your work in exercise Exercise 3.17.