Glossary
What is Euclid's algorithm?
Euclid's algorithm finds the greatest common divisor of two numbers m and n: divide m by n, and if the remainder r is zero, n is the answer; otherwise replace (m, n) with (n, r) and repeat. It is over two thousand years old and still the standard way to do it.
Why it works and how fast
Any number that divides m and n also divides r = m - qn, and the other way round, so (m, n) and (n, r) have the same common divisors. The numbers shrink every step, so it stops. It is fast: the worst case is consecutive Fibonacci numbers, so the number of steps grows only with the number of digits (Lamé's theorem).
Why Knuth starts with it
TAOCP opens, in §1.1, by writing Euclid's algorithm in his lettered-step style and using it to define what an algorithm is: finite, definite, with input, output and effective steps. Volume 2 comes back to it in §4.5.3 with a full analysis of how many steps it takes on average. The MIX playground has a graded gcd exercise.
Questions
What is the extended Euclidean algorithm?
The same loop, also tracking coefficients so that it returns x and y with mx + ny = gcd(m, n). It is how you compute modular inverses.