Edit made on January 28, 2009 by derekcouzens at 22:53:54
Deleted text in red /
Inserted text in green
Devised by Euclid, the Euclidean Algorithm is a method for finding
the greatest common divisor of two numbers.
Here's the algorithm:
* Let *a* and *b* be your starting numbers
* Compute *q* and *r* such that *a=qb+r* and *0<=r<b*
* Copy *b* into *a* and *r* into *b.*
* Repeat until *r=0.*
The value in *b* is now the /gcd/ of the original *a* and *b*.
As an example, consider 429 and 2002.
| *a* | = | *q* | * | *b* | + | *r* |
| 2002 | = | 4 | * | 429 | + | 286 |
| 429 | = | 1 | * | 286 | + | 143 |
| 286 | = | 2 | * | 143 | + | 0 |
Here we can see that gcd(429,2002) is 143.
You should check that:
* this is an algorithm in the technical sense
* the result always divides the original *a* and *b*
* every divisor of both *a* and *b* will divide the result.
* If !/ g=gcd(a,b) !/ then the /q/ in the algorithm can be used to compute /c/ and /d/ such that /g=ca+db./
* This algorithm can also be used to find the exact continued fraction of a square root.
* If !/ l=lcm(a,b) !/ then lg = ab
More if anyone asks.