The Euclidean Algorithm

Start with two numbers $a$ and $b$. Here are the steps in the Euclidean Algorithm for finding MATH.

  1. Divide $a$ by $b$ and take the remainder: $a=q_{1}b+r_{2}$

    (We take $r_{1}=b$, $r_{0}=a$).

  2. If the remainder is $0$ stop.

  3. If the remainder isn't $0$, divide it into the last thing you divided by, and take the new remainder, then go to step 2.

  4. $\gcd (a,b)=$ the last non-zero remainder




Example

$a=15$, $b=9$. Here are the steps:


MATH

Since $3$ is the last non-zero remainder, $\gcd (15,9)=3$.




Lemma

If $y=qx+r$ then MATH




Prove this by showing that anything that divides $x$ and $y$ must divide $x$ and $r$, and anything that divides $x$ and $r$ must divide $x$ and $y$. Thus MATH is a divisor of $x$ and $r$, so can't be bigger than $\gcd (x,r)$: MATH. Similarly, MATH. Thus, they are equal. (When you write this up, supply the reasons for each step.)




Here is what the Euclidean Algorithm looks like symbolically:


MATH

Thus, $\gcd (a,b)=r_{n}$ since $r_{n}$ is the last non-zero remainder.

  1. Use the lemma to show that each MATH for all $k $.

  2. Conclude that $r_{n}=\gcd (a,b)$.

Not only does the Euclidean Algorithm enable us to find the greatest common divisor of two numbers, but it tells us how to express this GCD as a linear combination of the two numbers. To see how this works, let's go back to the first example of $\gcd (15,9)$:


MATH

Using the second equation: $3=9-1\cdot 6$. Using the first equation, we can substitute for $6:$


MATH

Thus, we have expressed $3$ ($=\gcd (15,9)$) as a linear combination of $15$ and $9.$




  1. Use the Euclidean algorithm to find $\gcd (24,69)$, and express is as a linear combination of $24$ and $69$.

  2. Use the Euclidean algorithm to find $\gcd (252,198)$, and express is as a linear combination of $252$ and $198$.

  3. Use the symbolic form of the Euclidean algorithm (see above) to explain why you can always express $\gcd (a,b)$ as a linear combination of $a $ and $b$. If you have trouble with the subscripts and the general argument, try it for, say, $n=4$:


    MATH

    Write $r_{4}$ as a linear combination of $a$ and $b$. (You only need to use the first three equations.)

    (If you had similar trouble with Exercises 1 -- 3, do them just for the case $n=4$. You'll need all three equations, since the last one will give you the divisibility.)




The Euclidean Algorithm in Matlab

The gcd(a,b) command in Matlab can actually be used to find the GCD of $a$ and $b$ as a linear combination: you have to write it in a special way. Here's how it looks:

>> [d,x,y]=gcd(24,14)

d =

2

x =

3

y =

-5

This shows that the $d$, the $\gcd (24,14)$, is $2$, and can be written as MATH.