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?

number-theory gcd euclid-algorithm

1 Answer

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))

⬛