Euclidean Algorithm

This algorithm helps us determine the GCD of larger numbers efficiently.

Method (Euclidean Algorithm)

We can best do this by example. Consider

$$\gcd (85,19)$$

So, we have that

$$\begin{array}{rl}85& =\underline{4}\cdot 19+\underline{9}\\ 19& =\underline{2}\cdot 9+\underline{1}\\ 9& =\underline{1}\cdot 9+\underline{0}\end{array}$$

which is when it terminates. Thus, the $\gcd$ is $1$. We essentially reuse the GCD lemma. This leads us to the following:

Example 1

How many divisions do we need until we see a remainder of $0$ when we use the algorithm to compute

$$\gcd (150,90)$$

So,

$$\begin{array}{rl}150& =1\cdot 90+60\\ 90& =1\cdot 60+30\\ 60& =2\cdot 30+0\end{array}$$

So, $3$ total divisions. Our $\gcd (150,90)=30$.

Bezout’s Identity

Using the Euclidean Algorithm, we see that $\exists r,s\in \mathbb{Z}$ such that

$$\gcd (m,n)=mr+ns$$

Example 2

Find $r,s$ for

$$\gcd (54,15)$$

So,

$$\begin{array}{rl}54& =3\cdot 15+9\\ 15& =1\cdot 9+6\\ 9& =1\cdot 6+3\\ 6& =2\cdot 3+0\end{array}$$

So, the $\gcd$ is $3$. Now, working backwards from our work for GCD,

$$\begin{array}{rl}3& =1\cdot 9+(-1)\cdot 6\\ 6& =1\cdot 15+(-1)\cdot 9\\ 9& =1\cdot 54+(-3)\cdot 15\end{array}$$

So then,

$$\begin{array}{rl}3& =1\cdot 9+(-1)\left[1\cdot 15+(-1)\cdot 9\right]\\ & =2\cdot 9+(-1)\cdot 15\\ & =2\cdot \left[1\cdot 54+(-3)\cdot 15\right]+(-1)\cdot 15\\ & =2\cdot 54+(-7)\cdot 15\end{array}$$

and so our $r=2,s=-7$.

Example 3

Find Bezout coefficients for $\gcd (150,90)$.

So, from Example 1, we have

$$\begin{array}{rl}30& =(-1)\cdot 60+1\cdot 90\\ 60& =(-1)\cdot 90+1\cdot 150\end{array}$$

Then,

$$\begin{array}{rl}30& =(-1)\cdot 60+1\cdot 90\\ & =-[(-1)\cdot 90+1\cdot 150]+1\cdot 90\\ & =2\cdot 90+(-1)\cdot 150\end{array}$$

and so $r=2,s=-1$.