Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Algorithms
College Number Theory
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search