Proposition: Generating the Greatest Common Divisor Knowing Co-Prime Numbers

If \(c > 0\) is a common divisor of two integers \(a\) and \(b\), and if the integers $\frac ac$ and \(\frac bc\) are co-prime, then \(c\) is the greatest common divisor of \(a\) and \(b\), formally

\[c > 0\wedge c\mid a\wedge c\mid b\wedge \frac ac\perp \frac bc\Rightarrow c=\gcd(a,b).\]

Proofs: 1

Proofs: 1


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

Github:
bookofproofs


References

Bibliography

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