Proof
(related to Proposition: Generating the Greatest Common Divisor Knowing Co-Prime Numbers)
- By hypothesis, \(c > 0\) is a common divisor of two integers \(a\) and \(b\) and the integers \(\frac ac\) and \(\frac bc\) are co-prime.
- This means that \(\gcd\left(\frac ac,\frac bc\right)=1\).
- Therefore, at least one of the integers \(\frac ac\) and \(\frac bc\), and so at least one of the integers \(a\) and \(b\) must be different from zero.
- Set \(d:=\gcd(a,b)\), and we have $d\neq 0.$
- From the definition of the greatest common divisor we have that \(c\mid d\). Thus, \(\frac dc\) is an integer.
- Now, from the multiplication of rational numbers it follows that
\[\frac dc \frac ad=\frac ac,\quad\frac dc \frac bd=\frac bc,\]
which means that
\[\frac dc\mid \frac ac,\quad \frac dc\mid \frac bc.\]
- Because \(\gcd\left(\frac ac,\frac bc\right)=1\), \(d > 0\), \(c > 0\), any divisor of \(\gcd\left(\frac ac,\frac bc\right)\) must divide \(1\).
- This is only true for $\frac dc=1,$ which means that \(c=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