There are two ways to define the greatest common divisor (also known as greatest common factor, or highest common factor), both equivalent.

The first definition is as the name suggests: the GCD of $a$ and $b$ is the largest number which divides both $a$ and $b$.

The second definition is the more "mathematical", because it generalises to arbitrary rings rather than just ordered rings. The GCD of $a$ and $b$ is the number $c$ such that $c\mid a$, $c\mid b$, and whenever $d\mid a$ and $d\mid b$, we have $d\mid c$. (That is, it is the maximal element of the partially ordered set that consists of the divisors of $a$ and $b$, ordered by division.)

Examples

Equivalence of the definitions

Relation to prime factorisations

Calculating the GCD efficiently