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

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

◀ ▲ ▶Branches / Number-theory / Proof

Proof

References

Bibliography