# What is Euclid's algorithm?

> Euclid's algorithm finds the greatest common divisor by repeated remainders. Why it works, how fast it is, and why Knuth opens TAOCP with it.

**Euclid's algorithm**: Euclid's algorithm computes the greatest common divisor of two positive integers by repeatedly replacing the larger with its remainder modulo the smaller until the remainder is zero.

**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](https://cracked.guide/guide/knuth-w017-0), 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](https://cracked.guide/guide/knuth-w066-0) with a full analysis of how many steps it takes on average. The [MIX playground](https://cracked.guide/mix) 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.

---

Source: https://cracked.guide/glossary/euclids-algorithm
cracked.guide: A free, dated 145-week path to getting genuinely cracked at programming.