Euclid's Algorithm
Iterated division with remainder reaches in fewer than steps, and the last nonzero remainder satisfies .
Theorem 4.8
The output of Euclid’s algorithm with input is .
Termination
The remainders produced by the algorithm satisfy
so each step strictly decreases the remainder. In particular the algorithm terminates in steps.
Example
To compute , run the algorithm:
The output is the last non-zero remainder, so .
Related
Stated in
- Theorem 4.8§4.3 Euclid’s Algorithm