Euclidean Algorithm

Numerical Example

We have seen in the theorem, we can represent the greatest common divisor of two integers as a linear combination of them, and it is actually the smallest positive linear combination. The question is, how can we find such a linear combination, and how can we find the greatest common divisor efficiently?

We can take two numbers $a=324$ and $b=148$ as an example. One naive idea is use subtraction repeatedly to find make the number smaller but remains positive. The following table shows the process:

Step	$a$	$b$	$a-b$
1	324	148	176
2	176	148	28
3	148	28	120
4	120	28	92
5	92	28	64
6	64	28	36
7	36	28	8
8	28	8	20
9	20	8	12
10	12	8	4
11	8	4	4
12	4	4	0

As the process terminates, we find the greatest common divisor of $324$ and $148$ is $4$, and we took $12$ steps to find it. This methodology will always work, but it is not very efficient.

The Euclidean Algorithm is an improved version of the above process, it reduces the number of steps needed to find the greatest common divisor, with the price of doing division instead of subtraction. The following table shows the process of the Euclidean Algorithm:

Step	$a$	$b$	$a=bq+r$	$r$
1	324	148	324 = 148 * 2 + 28	28
2	148	28	148 = 28 * 5 + 8	8
3	28	8	28 = 8 * 3 + 4	4
4	8	4	8 = 4 * 2 + 0	0

With the Euclidean Algorithm, we only need $4$ steps to find the greatest common divisor of $324$ and $148$. The process is replacing the dividend with the divisor, and the divisor with the remainder, and repeat the process until the remainder becomes $0$. The greatest common divisor is the last non-zero remainder.

Euclidean Algorithm

The Euclidean Algorithm can be formally stated as follows:

Theorem

Let $a$ and $b$ be two integers, with $a\ge b$ and both positive. Then the greatest common divisor of $a$ and $b$ can be found by the following process:

$$\begin{array}{rl}a& =b{q}_1+r_1,0\le r_1<b,\\ b& =r_1{q}_2+r_2,0\le r_2<r_1,\\ r_1& =r_2{q}_3+r_3,0\le r_3<r_2,\\ & ⋮\\ r_{n-2}& =r_{n-1}{q}_n+r_n,0\le r_n<r_{n-1},\\ r_{n-1}& =r_n{q}_{n+1}+0.\end{array}$$

The greatest common divisor of $a$ and $b$ is $r_n$.

Proof of Correctness

The idea this time is to show the greatest common divisor of the pairs of numbers remain the same throughout the process. The process in the Euclidean Algorithm is recursive, so it is sufficient to show the invariance of the greatest common divisor for one step. We state it as a lemma:

Lemma

Let $a,b$ be positive integers, and let $q,r$ such that $a=bq+r$, and $0\le r<b$. Then the greatest common divisor of $a$ and $b$ is the same as the greatest common divisor of $b$ and $r$.

Proof of Lemma

We will show the pair $a,b$ and $b,r$ share the same exact set of divisors. We will show two directions:

1. If $c\mid a$ and $c\mid b$, then $c\mid r$.
2. If $c\mid b$ and $c\mid r$, then $c\mid a$.

The first direction is easy, if $c\mid a$ and $c\mid b$, then $c\mid a-bq=r$ by this property.

For the second direction is less obvious, if $c\mid b$ and $c\mid r$, then we can write $b=c{t}_1$ and $r=c{t}_2$. Then we have:

$$\begin{array}{rl}a& =bq+r\\ & =c{t}_{1}q+c{t}_2\\ & =c(t_{1}q+t_2).\end{array}$$

This implies $c\mid a$.

Therefore, the greatest common divisor of $a$ and $b$ is the same as the greatest common divisor of $b$ and $r$. $■$

Warning

Make sure you know how to prove this property.

Warning

GCD is not in general stable under linear combinations, find examples such that:

$$\gcd (a,b)\ne \gcd (ma+nb,b).$$

Can you figure out a condition on $m,n$ such that the equality holds?

Proof of Theorem

$$\begin{array}{rl}(a,b)& =(b,r_1)\\ & =(r_1,r_2)\\ & =\cdots \\ & =(r_{n-1},r_n)\\ & =(r_n,0)\\ & =r_n.\end{array}$$

This completes the proof of the Euclidean Algorithm. $■$

Backtracking to Find the Linear Combination

As we mentioned in the lecture, the Euclidean Algorithm not only returns the greatest common divisor, but also the linear combination of the two numbers. We can backtracking the table to find the linear combination:

$$\begin{array}{rl}4& =4-0\\ & =8-4\\ & =8-(28-3\cdot 8)\\ & =-28+4\cdot 8\\ & =-28+4\cdot (148-5\cdot 28)\\ & =4\cdot 148-21\cdot 28\\ & =4\cdot 148-21\cdot (324-2\cdot 148)\\ & =-21\cdot 324+46\cdot 148\end{array}$$

You could also backtraking the first table to find the linear combination.