## Most recent change of EuclideanAlgorithm

Edit made on January 28, 2009 by DerekCouzens at 22:53:54

Deleted text in red / Inserted text in green

WW
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.

----
!! Extras
* 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