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.

Show all work and steps please. Cite proofs if needed

Solution

BY Euclidean Algorithm there exist, x, y integers so that

px+qy=gcd(p,q)

Since, gcd(p,q) =1 So there exist ,x,y (which can be found using Euclid Algorithm)

so that

px+qy=1

MUltiplying by r on both sides gives

p(xr)+q(yr)=r

So, m=xr,n=yr are solutoins to

mp+nq=r

Hence proved