## Proof That Two Numbers Divided by Their Greatest Common Divisor are Relatively Prime

If

\[a, \; b\]

are integers with greatest common divisor \[d\]

then the greatest common divisor of \[\frac{a}{d}, \; \frac{b}{d}\]

is 1.Proof

If the greatest common divisor of

\[a, \; b\]

is d then we can find integers \[m, \; n\]

such that \[am+bn=d\]

. Dividing by \[d\]

gives \[\frac{a}{d}m+ \frac{b}{d}n=1\]

. Then by this theortem \[\frac{a}{d}, \; \frac{b}{d}\]

have greatest common divisor 1 and are relatively prime.