The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
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,

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 

- Doctor Rob, The Math Forum   
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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.