Euclidean algorithm

Summary

The Euclidean algorithm computes the greatest common divisor of two natural numbers $a$ and $b$. It uses two rules: $\gcd(a, 0) = a$, and $\gcd(a, b) = \gcd(b, a \bmod b)$ when $b \neq 0$. It applies the second rule until the second number is $0$. Then the first number is the result. The algorithm stops, because the second number gets smaller at each step.