Support Ukraine 🇺🇦Help Ukrainian ArmyHumanitarian Assistance to Ukrainians

Proof of Euclid's Algorithm

Sam

Oct 05 2020 at 12:47 GMT

According to Euclid's Algorithm, the greatest common divisor (gcd) of two integers $a$ and $b$, where $b \ne 0$, is equal to the greatest common divisor of $b$ and the remainder of dividing $a$ by $b$. Symbolically:

$\gcd(a, b) = \gcd(b, \text{rem}(a, b)) \ \forall a \in \Z, \forall b \in \Z_{\ne 0}$

How can we prove this?

Carl

Oct 05 2020 at 13:55 GMT

Before providing the proof for Euclid's algorithm, there will be a few preliminary definitions, a theorem, and a lemma.

Definition of divides. We say that an integer $a$ divides an integer $b$ if and only if $a$ multiplied by some integer $k$ is equal to $b$:

$a \mid b \iff \exists k \in \Z : ak =b$

The symbol $|$ is a shorthand for divides.

Definition of integer linear combination. An integer linear combination of two integers $a$ and $b$ is an expression of the form $sa+tb$, where $s$ and $t$ are some integers.

Since we are working with integers, from now on I will refer to integer linear combination as just linear combination.

Division Theorem. Given an integer $n$ and a non-zero integer $d$ (the divisor), there exists a unique pair of integers $q$ (the quotient) and $r$ (the remainder) with $0 \le r < \left|d\right|$ such that $n$ is equal to the product $qd$ plus the remainder $r$:

$\forall n \in \Z, \forall d \in \Z_{\ne 0}, \exists! q, r \in \Z : n = qd + r \text{ with } 0 \le r < \left|d\right|$

I will not provide the proof for this theorem, but you can look it up.

Lemma 1. If an integer $a$ divides an integer $b$, and it also divides another integer $c$, then $a$ divides any linear combination of $b$ and $c$:

$(a \mid b) \land (a \mid c) \implies a \mid sb + tc \ \ \forall s, t \in \Z$

Proof of Lemma 1. Assume that $a \mid b$ and $a\mid{c}$. Since $a\mid{b}$, there exists an integer $k_1$ such that $ak_1=b$. Likewise, since $a\mid{c}$, there exists an integer $k_2$ such that $ak_2=c$.

Let $sb+tc$ be any linear combination of $b$ and $c$. We can rewrite it in terms of $a$:

\begin{aligned} sb + tc &= s(ak_1) + t(ak_2) \\ &= a(sk_1) + a(tk_2) \\ &= a(sk_1 + tk_2) \end{aligned}

Since $a$ multiplied by some integer is equal to $sb+tc$, it means that $a$ divides $sb+tc$.

Finally, let's get to the proof of Euclid's algorithm, which I restate for convenience:

$\gcd(a, b) = \gcd(b, \text{rem}(a, b)) \ \forall a \in \Z, \forall b \in \Z_{\ne 0}$

Euclid's algorithm Proof. By the Division Theorem, we know that there exists a unique pair of integers $q$ and $r$ such that $a$ is equal to the product of the quotient $q$ and $b$ plus the remainder $r$:

$\exists! q, r: a = qb + r \text{ with } 0 \le r < \left|b\right|$

$r$ is by definition $\text{rem}(a,b)$. We can express $r$ in terms of $a$ and $b$ by rearranging the above equation:

\begin{aligned} a &= qb + r \\ r &= a - qb \\ r &= a + (-q)b \\ \text{rem}(a, b) &= a + (-q)b \end{aligned}

Thus, we found that $\text{rem}(a,b)$ is a linear combination of $a$ and $b$.

Since $\gcd(a,b)$ divides both $a$ and $b$, it also divides any linear combination of $a$ and $b$ (by Lemma 1).

Therefore, $\gcd(a,b)$ divides $\text{rem}(a,b)$.

$\gcd(a, b) \mid \text{rem}(a, b)$

This and the fact that $\gcd(a,b) \mid b$ tells us that $\gcd(a,b)$ is a common divisor of $b$ and $\text{rem}(a,b)$, which means that it has to be less than or equal to $\gcd(b, \text{rem}(a, b))$:

$\gcd(a, b) \le \gcd(b, \text{rem}(a, b))$

Also, since $a$ is a linear combination of $b$ and $\text{rem}(a,b)$, the $\gcd(b,\text{rem}(a,b))$, which divides both $b$ and $\text{rem}(a,b)$, must divide $a$.

$\gcd(b, \text{rem}(a, b)) \mid a$

This means that $\gcd(b,\text{rem}(a,b))$ is a common divisor of $a$ and $b$, and so it has to be less than or equal to the greatest common divisor of $a$ and $b$.

$\gcd(b, \text{rem}(a, b)) \le \gcd(a, b)$

Therefore, since $\gcd(a,b)$ is less than or equal to $\gcd(b,\text{rem}(a,b)$ and vice versa, they have to be equal.

$\gcd(a, b) = \gcd(b, \text{rem}(a, b))$