# Greatest common divisor

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

show the two different definitions in action and how they prepare

# Equivalence of the definitions

prove this

# Relation to prime factorisations

algorithm given access to prime factorisations; explain why this is unhelpful

# Calculating the GCD efficiently

link to Euclidean algorithm

Children:

- Bézout's theorem
Bézout’s theorem is an important link between highest common factors and the integer solutions of a certain equation.

Parents:

- Mathematics
Mathematics is the study of numbers and other ideal objects that can be described by axioms.