[summary: The greatest common divisor of two natural numbers is the largest number which divides both of them.]
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.)
[todo: show the two different definitions in action and how they prepare]
Equivalence of the definitions
[todo: prove this]
Relation to prime factorisations
[todo: algorithm given access to prime factorisations; explain why this is unhelpful]
Calculating the GCD efficiently
[todo: link to Euclidean algorithm]