Editing EuclideanAlgorithm
You are currently not logged in.
To change this, fill in the following fields:
Username
Password
If you want a password, email topicsinmaths@solipsys.co.uk
Who can read this page?
The World
Members
Council
Admin
You have been granted an edit lock on this page
until Fri Apr 19 09:15:30 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 highest common factor (also know as 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 in turn can be used to show that working in modulo arithmetic, every non-zero number has a multiplicative inverse $mod~p,$ when $p$ is a prime number. * This algorithm can also be used to find the exact continued fraction of a square root. * If $l=lcm(a,b)$ and $g=gcd(a,b),$ then $lg=ab.$