Editing EuclideanAlgorithm
You are currently not logged in.
To change this, fill in the following fields:
Username
Password
Who can read this page?
The World
Members
Council
Admin
You have been granted an edit lock on this page
until Fri Apr 19 23:33:10 2024.
Press
to finish editing.
Who can edit this page?
World editing disabled
Members
Council
Admin
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.