Prove that for every pair of positive integer p and q that h

Prove that for every pair of positive integer p and q that have no prime factors in common, and every other positive integer r, there are integers m and n such that mp + nq = r.

Solution

If, p and q hae no prime factors in common ie gcd(p,q)=1

Then by Euclid Algorithm we can find x,y integers so that

px+qy=1

Multipying by r gives

p(xr)+q(yr)=r

So, m=xr,n=yr

SUch integers exist for each integer r