Greatest Common Divisor

The greatest common divisor of two integers $a$ and $b$, written $\gcd(a, b)$, is the largest positive integer that divides both $a$ and $b$.

The Euclidean algorithm computes the GCD efficiently: $\gcd(a, b) = \gcd(b, a \bmod b)$, terminating when the remainder reaches zero. This algorithm also yields a representation $\gcd(a, b) = sa + tb$ for some integers $s$ and $t$ (Bézout’s identity).

In the divisibility lattice on positive integers, $\gcd(a, b)$ is the meet of $a$ and $b$.