Explaining the Euclidean Algorithm

Date: 10/27/98 at 08:49:31
From: Megan 
Subject: Analysis, prime factorization

There is an algorithm for prime factorization called the Division 
Algorithm. Given integers s and t, t > 0, there exist unique integers 
q and r such that s = t*q + r and 0 =< r < t.

We need to find the GCF of both numbers. For example, to find the GCF 
of 54 and 198 by the division algorithm, divide 198 by 54. Repeat the 
process using the divisor as the new dividend and the remainder as the 
new divisor:

   198 = 3*54 + 36
    54 = 1*36 + 18
    36 = 2*18 + 0

When we get 0 as the remainder, the last divisor, here 18, is the GCF 
of the given integers. The procedure is called the Euclidean algorithm. 
I need to know why this algorithm works. What is the explanation for 
why these particular steps give you the GCF of the two numbers? 

Thanks a lot,
Megan

Date: 10/27/98 at 09:19:09
From: Doctor Rob
Subject: Re: Analysis, prime factorization

At each step, you can show that if d divides the divisor t and the
dividend s, it also divides the remainder r. If d divides t, write
t = d*T. If d divides s, write s = d*S. Then using the equation:

   r = s - q*t
   r = d*S - q*d*T
   r = d*(S - q*T)
   r = d*R

and so d divides r, too.

This shows that any common divisor of the first two numbers must also
divide the last divisor, by working down the chain of equations one at 
a time. (You can use the Principle of Mathematical Induction on the 
number of steps to make this into a proof.)

Similarly, if d divides the divisor t and the remainder r, it also 
divides the dividend s. Write t = d*T, r = d*R. Then:

   s = q*t + r
   s = q*d*T + d*R
   s = d*(q*T + R)
   s = d*S

and so d divides s, too.

This shows that any factor of the last divisor, including that last 
divisor itself, also divides both of the first numbers, by working up 
the chain of equations one step at a time. (You can make this into a 
proof using the Principle of Mathematical Induction, too.)

Put these two parts together to conclude that the greatest common 
divisor of the two numbers equals the last divisor in the Euclidean 
Algorithm.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/