CMSC 27100 — Lecture 7

Here is the proof of Euclid’s algorithm’s correctness, i.e. the fact that \[\gcd(a,b) = \begin{cases} a & \text{if $b = 0$,} \\ \gcd(b, a \mathop{\mathbf{mod}} b) & \text{otherwise.} \end{cases}\]

Let $a$ and $b \gt 0$ be arbitrary. Let $q$ and $r$ be such that $a = qb + r$ by the Division Theorem. Since $d = \gcd(a,b)$, we have $d \mid a$ and $d \mid b$. Then $d \mid qb$ by divisibility of integer combinations. Putting this together, we have $d \mid a - qb$ and therefore $d \mid r$. Therefore $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$ and therefore, $c \mid a$. That is, $c$ is also a common divisor for $a$. Since $c$ is a common divisor of $a$ and $b$, this means we must have $c \leq d = \gcd(a,b)$. And since $c$ was arbitrary, we must have that every common divisor $c$ of $b$ and $r$ is at most $d$. Therefore, $\gcd(b,r) = d = \gcd(a,b)$.

Before talking about the complexity of Euclid’s algorithm, we’ll take some time to prove one more useful property of the gcd. From the Division Theorem, we get the following result.

For all integers $a$ and $b$, there exist integers $x$ and $y$ such that $\gcd(a,b) = a \cdot x + b \cdot y$.

This result is commonly referred to as Bézout’s lemma or Bézout’s identity, attributed to Étienne Bézout, a French mathematician in the mid-1700s. We’ll continue to do so, but like many other results you’ll encounter, the result was known before.

Working backwards, we quickly find that the result is found due to Bachet de Méziriac, another French mathematician in around 1600. But in fact, we can go even further back: a constructive proof of this result dates back to about 500 AD via the Indian mathematician Āryabhaṭa and the first mention of the result can be found due to Euclid in about 300 BC (who we will be seeing a lot of).

Like the Division Theorem, there are constructive and non-constructive proofs of Bézout’s lemma. The constructive proof is via an algorithm called the Extended Euclidean Algorithm, which can be obtained by extending the Euclidean algorithm from above. However, we’ll take the opportunity to introduce the notion of non-constructive proof and proof by contradiction.

Proving negation

Though there is a constructive proof due to Āryabhaṭa found in the textbook, the proof that we’ll go through is a non-constructive proof. When we proved the Division Theorem, we showed the existence of integers $q$ and $r$ by showing explicitly how to compute them. Here, we’ll use a different tactic, a proof by contradiction.

Let’s outline the general logical foundations for this approach. First, we have to ask ourselves what it means to prove that a statement is false. With other propositions we’ve seen, like $p \wedge q$ or $p \rightarrow q$, we construct their proofs using proofs of $p$ and $q$, the constituent parts of the proposition. However, for a proposition like $\neg p$, we only have the proposition $p$ and it’s clear that a proof of $p$ would not let us prove $\neg p$.

Are there things that we know definitely can’t be true? Yes! Consider the proposition $p \wedge \neg p$. This proposition can’t be true because it can never be the case that both $p$ and $\neg p$ are true. Any proposition of this form is called a contradiction.

For any proposition $p$, the proposition $p \wedge \neg p$ is said to be a contradiction, and is denoted $\bot$.

The approach to proving $\neg p$ is show that it cannot be the case that $p$ can be proven. What does that look like?

  1. Assume that $p$ is true.
  2. Reason using the assumption that $p$ is true and arrive at a contradiction.
  3. Contradictions cannot occur. The assumption that $p$ is true created the conditions that allowed us to come up with a contradiction. Therefore, $p$ cannot be true.

The inference rule for this is \[\frac{\boxed{\begin{matrix}p \\ \vdots \\ \bot \end{matrix}}}{\neg p} \neg i\] In other words, a proof of $\neg p$ is a proof of the implication $p \rightarrow \bot$. One way to think of this is that $\neg p$ is a refutation of $p$.

Let’s proceed with the proof of Bézout’s identity; that for all integers $a$ and $b$, there are integers $x$ and $y$ such that $\gcd(a,b) = ax + by$.

If $a = b = 0$, then any $x$ and $y$ works. So without loss of generality, we have non-zero $a$ or $b$. Consider all integers of the form $ax + by$ for all integers $x$ and $y$. Let $d = am + bn$ be the least positive integer of this form where $m$ and $n$ are integers.

First, we will show that $d$ is a common divisor of $a$ and $b$. Suppose it isn’t. That is, we assume that $d$ isn’t a common divisor of $a$ and $b$. Without loss of generality, say $d \nmid a$. Then by the Division Theorem, there exist integers $q$ and $r$ such that $a = q \cdot d + r$ and $d \gt r \gt 0$. Then we have \begin{align*} r &= a - q \cdot d \\ &= a - q \cdot (am + bn) \\ &= (1-qm)a + (-nq)b \end{align*} This gives us that $r$ is an integer of the form $ax+by$. But since $0 \lt r \lt d$, this contradicts our assumption that $d$ was the least positive integer of that form. Therefore, $d$ must be a common divisor of $a$ and $b$.

Now that we know $d$ is a common divisor, it remains to show that $d$ is the greatest common divisor of $a$ and $b$. So consider any common divisor $c$ of $a$ and $b$. Then there exist integers $s$ and $t$ such that $a = cs$ and $b = ct$. This gives us \begin{align*} d &= am + bn \\ &= csm + ctn \\ &= c \cdot (sm + bn) \end{align*} Therefore, $c \mid d$ and therefore $c \leq |d|$. Thus, $d = \gcd(m,n)$.

There are some subtle assumptions that we made that are easy to miss and worth discussing.

Well ordering

First, notice that we considered a collection of integers of the form $ax+by$ and assumed the existence of a least positive integer. The existence of such an integer comes from the following property.

Every nonempty set of nonnegative integers has a smallest element.

This is often taken as an axiom of the natural numbers, but it turns out the property is equivalent to the axiom of induction. This means that from induction, one can prove well-ordering and vice-versa—one can derive induction given well-ordering as an axiom.

The well ordering of the integers is a property that is typically used in conjunction with indirect proofs. You can find more about well ordering proofs in Chapter 2 of the text.

Proof by contradiction

There’s another assumption that we snuck in. Our assumption in the proof above was that $d$ was not a common divisor of $a$ and $b$. This is a proposition of the form $\neg p$. We then used this assumption to arrive at a contradiction. According to our rules, this means that we now have a proof of $\neg \neg p$.

Are $p$ and $\neg \neg p$ the same thing? In classical logic, this is the case. But consider the following interpretation for inference rules. We’ve said that an inference rule says that if we have proofs of the statements on the top, this allows us to construct a proof for the statement on the bottom. This is the intuitionist or constructivist interpretation of logic.

If we think a few steps more, we see that in this interpretation, we can view this as a computation. An inference rule describes consuming proofs of a certain type in order to construct a proof of a certain type. Since the proofs are necessary ingredients for the computation and construction of a new proof, we really need to have such proofs in hand.

It’s not too hard to see that if we have a proof of $p$, we also have a proof of $\neg\neg p$:

  1. Assume $\neg p$.
  2. But we have a proof of $p$.
  3. This gives us $p \wedge $\neg p$, a contradiction.
  4. We conclude $\neg \neg p$ by applying $\neg i$ to the statement $\neg p$.

But what about the other way around? Is having a proof of $\neg \neg p$ good enough to use as a proof of $p$? What we really have is a proof that it can’t be the case that there’s a proof of $\neg p$, which is a proof that it can’t be the case that there’s a proof of $p$. But we are still without a proof of $p$.

Another way is to consider the question of the law of excluded middle (LEM), which is the statement $p \vee \neg p$. In classical logic, this is obviously true—in fact, it’s an axiom. It must be the case that $p$ is either true or false. But the intuitionist interpretation of this statement is “it must be the case that we have a proof of $p$ or a proof of $\neg p$”. This is not always true—there are many statements for which we have no proof either way.

So a proof system for classical logic is one that includes an inference rule for LEM, while intuitionists would reject it. \[\frac{}{p \vee \neg p} \mathrm{LEM}.\] Using LEM, one can then derive the rule \[\frac{\neg \neg p}{p} \neg\neg e,\] that one can prove $p$ from its double negation. This rule can then be used to derive the rule \[\frac{\boxed{\begin{matrix}\neg p \\ \vdots \\ \bot \end{matrix}}}{p} \mathrm{PBC},\] where PBC stands for “proof by contradiction”.