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

### Euclidean Algorithm

```
Date: 5/13/96 at 9:43:26
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,
```

```
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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search