If m and n are any two positive integers show that mgcdm n a

If m and n are any two positive integers, show that m/gcd(m, n) and n/gcd(m, n) are relatively prime. (Hint: use the result of Euclid\'s algorithm.)

Solution

By Euclid’s algorithm, there exist integers u and v such that

um + vn = gcd(m,n).

Dividing both sides by gcd(m,n) gives u(m/gcd(m,n)) + v(n/gcd(m,n)) = 1.
So by Euclid algorithm, m/gcd(m,n) and n/gcd(m,n) are relatively prime (note that both are integers by definition of gcd).