Euclidean AlgorithmDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/