Editing EuclideanAlgorithm
You are currently browsing as guest..
To change this, fill in the following fields:
Username
Password
Click here to reset your password
Who can read this page?
The World
Members
Council
Admin
You have been granted an edit lock on this page
until Fri Mar 29 05:06:18 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.