# Proof that any number can be represented as the sum of two relatively prime numbers that are each multiplies by some integer.

The question that I am being asked is as follows: "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."

This is not a homework or test question, it is a review question that I am stuck on.

I have gathered that I am supposed to apply the prime factorization theorem and the quotient-remainder theorem in some way, but I am completely stumped. I have gotten no farther than stating the premise and what it means mathematically to be relatively prime numbers. Any help would be much appreciated.

• Can you first show that there exist $m,n$ for which $mp+nq=1$? Commented Dec 13, 2016 at 0:12
• Do you know the Euclidean algorithm? Commented Dec 13, 2016 at 0:12
• ... or Bézout's identity? Commented Dec 13, 2016 at 0:14

We have $\gcd (p,q) = 1$. By Bezout's identity, there are integers $m,n$ such that $mp + nq = 1$. Then \begin{align*} r(mp + nq) &= r(1) \\ rmp + rnq &= r \\ (rm)p + (rn)q &= r \text{,} \end{align*} so $rm$ and $rn$ are such a pair of numbers.
Say we don't have Bezout's identity. How would we obtain it? We would use the Extended Euclidean Algorithm to find $m$ and $n$.