# Proof: Commutativity of the Greatest Common Divisor

(related to Proposition: 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).$

Github: ### References

#### Bibliography

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