Proof: Commutativity of the Greatest Common Divisor

Assume $a,b$ are integers and $D_{a,b}$ is a set defined by $D_{a,b}:=\left\{d\in\mathbb Z : d\mid a\wedge d\mid b\right\}.$
$\mathbb N\cap D_{a,b}$ is not empty, since it contains e.g. the number $1.$
Moreover, $\mathbb N\cap D_{a,b}$ is finite, since it is the subset of the intersection of the sets of natural numbers $\mathbb N$, the set of divisors $D_a$ of $a$ and the set of divisors $D_b$ of $b$, both intersections $\mathbb N\cap D_a$ and $\mathbb N\cap D_b$ have only a finite number of divisors and any subset of a finite set is finite.
From the existence and uniqueness of a maximum in subsets of natural numbers it follows that $\mathbb N\cap D_{a,b}$ contains a maximum $m_0$.
Thus, $\gcd(a,b):=m_0$ exists and is unique.
It is clear that $\gcd(a,b)\mid a$ and $\gcd(a,b)\mid b$, since $\gcd(a,b)\in D_{a,b}.$
It remains to be shown that other common divisor $d\in D_{a,b}$ divides the greatest common divisor, i.e. we have $d\mid \gcd(a,b)$ for all $d\in D_{a,b}.$
- From $d\mid a$ and $d\mid b$ it follows that $a\mid a\frac{b}{d}$ and $b\mid b\frac{a}{d}.$
- This means that $\frac{ab}d$ is a common multiple of $a$ and $b.$
- Let $m:=\frac{ab}{\gcd(a,b)}$, i.e. $ab=m\gcd(a,b).$
- Therefore, since $m\mid ab$ it follows even $m\mid \frac{ab}d$ since $\frac{ab}d$ is a common multiple of $a$ and $b.$
- This is equivalent to $\frac{ab}{\gcd(a,b)}\mid \frac{ab}d$, therefore the number $\frac{\gcd(a,b)}{d}$ is an integer.
- This shows that $d\mid\gcd(a,b).$
  ∎

Thank you to the contributors under CC BY-SA 4.0!

Landau, Edmund: "Vorlesungen über Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927