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
50 PRINT" THE HCF IS-";B
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!  http://mathforum.org/dr.math/