GCD Proof to find all integers that satisfy $am + bn = \gcd(a, b)$

Question

I have this question that I'm not entirely sure how to answer.

Suppose that $a, b$ are non-zero integers. Find all integers $m, n$ such that $am + bn = \gcd(a, b)$

I know that it suffices to show that if $m, n$ and $m', n'$ are 2 possible solutions that showing that $\frac{b}{\gcd(a, b)}\mid m-m'$ and $\frac{a}{\gcd(a, b)}\mid n-n'$. However, I'm not entirely sure how to get there. Thanks.

Answer 1

Let $c = \text{gcd}(a,b)$.

• Hint 1: Start with $am + bn = c$ and $am' + bn' = c$. What happens if you combine these equations?
• Hint 2: What is the value of $\text{gcd}(a/c, b/c)$?
• Hint 3: If $x \mid yz$ and $\text{gcd}(x,y) = 1$, what is the relationship between $x$ and $z$?