# Greatest common divisor

https://arbital.com/p/greatest_common_divisor

by Patrick Stevens Jul 28 2016 updated Aug 4 2016

The greatest common divisor of two natural numbers is… the largest number which is a divisor of both. The clue is in the name, really.

[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.)

# Examples

[todo: show the two different definitions in action and how they prepare]

# Equivalence of the definitions

[todo: prove this]