# Proof

• Let $$a > 0$$, $$b > 0$$ be natural numbers.
• Since $$ab$$ is a common multiple of $$a$$ and $$b$$, it follows from the proposition about the least common multiple that $\operatorname{lcm}(a,b)\mid ab.$
• We set $$d:=\frac{ab}{\operatorname{lcm}(a,b)},\quad\quad( * )$$ and will show that $$d$$ is the greatest common divisor of $$a$$ and $$b$$, i.e. $d=\gcd(a,b).$
• From the definition of multiplication of rational numbers it follows that we can transform the equation $$( * )$$ into $\frac{a}{d}=\frac{\operatorname{lcm}(a,b)}{b},~\frac{b}{d}=\frac{\operatorname{lcm}(a,b)}{a}.$
• Since $$a$$ and $$b$$ divide $$\operatorname{lcm}(a,b)$$ , the fractions $$\frac{a}{d}$$ and $$\frac{b}{d}$$ are, in fact, integers.
• Therefore, $$d$$ is a common divisor of $$a$$ and $$b$$.
• It remains to be shown that $d$ is the greatest common divisor of $$a$$ and $$b$$. * Let $$f$$ be any common divisor of $$a$$ and $$b$$. * Because $a\mid a\frac bf$ and $b\mid b\frac af,$ the number $$\frac{ab}f$$ is a common multiple of $$a$$ and $$b$$. * It follows from the proposition about the least common multiple that $$\operatorname{lcm}(a,b)$$ divides $$\frac{ab}f$$. * Since $$\operatorname{lcm}(a,b)=\frac{ab}d$$ (see above), we have that $\frac{ab}d|\frac{ab}f.$ * This means that the rational number $\frac{\frac{ab}f}{\frac{ab}d}=\frac df$ is in fact an integer. * Since $$f$$ was an arbitrarily chosen common divisor of both, $$a$$ and $$b$$, and since it divides the common divisor $$d$$, the latter number $$d$$ must be the greatest common divisor. * It follows that $d=\gcd(a,b).$

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

Github:

### References

#### Bibliography

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