WW

HEADERS_END

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.

----

Enrichment Task

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

More if anyone asks.