The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Euclidean Algorithm

Date: 5/13/96 at 9:43:26
From: Farhad Mehta
Subject: Euclidean Algorithm

How can we prove that Euclid's method for finding the highest common
factor for two numbers will work for all values?

The steps in a basic programming language are -

10 input "the two numbers:";A,B
20 R=A MOD B
30 IF R=0 THEN  ELSE 40
40 A=B:B=R:GOTO 20
60 END

Thanking you,
Farhad Mehta

Date: 12/11/96 at 01:04:52
From: Doctor Rob
Subject: Re: Euclidean Algorithm

Euclid's method is also called the Euclidean algorithm. It works to 
find the highest common factor (HCF), otherwise called the greatest 
common divisor (GCD), whenever you give it two positive integers.

The proof of that fact goes sort of like this: First you show that if
D divides the inputs A and B, then it also divides R. Since this works
at every single step of the algorithm, when you are done, the last R 
will also be divisible by D. This proves that the output is divisible 
by the HCF of the inputs. Second you work backwards, showing that the 
output divides both the A and B of the last step, then showing that it 
also divides the A and B of the next-to-last step, and so on. When you 
are done, you will have shown that the output divides both A and B, so 
it is a common factor, so it must divide the HCF. Thus, if the output 
both divides and is a divisor of the HCF, they must be equal.

I hope you can fill in the details, given this sketch of a proof.

-Doctor Rob,  The Math Forum
 Check out our web site!   
Associated Topics:
College Algorithms
College 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.