Greatest Common Divisor question

Question

Let $m$ and $n$ be natural numbers. How many pairs $x$ and $y$ of natural numbers with $m\cdot x+n\cdot y=m\cdot n$ are there ?

Answer 1

I think MLT's comment is pretty much the answer. Since he gave two points that make a line segment of our interest, the problem is to count the integer points on the segment.

---

Draw a plane and see that $mx + ny = mn$ is a line that passes $(n, 0), (0, m)$. Any pair of natural number $(x, y)$ must be on this line segment. We already obtained two points precisely when $y = 0$ and $x = 0$. Without loss of generality, we may assume that these cannot happen simultaneously.

Let's solve the case when $m, n$ are coprime. It is intuitively clear that there is no more than the two trivial points that the line passes on the first quadrant. If not, we have a nontrivial solution $(x_{0}, y_{0}) \in \mathbb{Z}_{+} \times \mathbb{Z}_{+}$ so that $mx_{0} = n(y_{0} - m)$, so by Eucild's lemma, $n | x_{0}$. By symmetry, we must have $m | y_{0}$, so we may write $x_{0} = nx_{1}$ and $y_{0} = my_{1}$ for some nontrivial $x_{1}, y_{1}$. This gives a contradiction since $mnx_{1} + mny_{1} = mx_{0} + ny_{0} = mn$ implies $x_{1} + y_{1} = 1$.

Now let's move on to the general case. Let $d$ be the greatest common divisor of $m, n$ and write $m = dm_{0}$ and $n = dn_{0}$, where $m_{0}, n_{0}$ are coprime. Then we may seek solutions to $m_{0}x + n_{0}y = dm_{0}n_{0}$. We go over the same proof again with some modification. Suppose that $(x_{0}, y_{0})$ is a nontrivial solution so that $x_{0}, y_{0} \neq 0$. Then $mx_{0} = n_{0}(dm_{0} - y_{0})$, so $n_{0} | x_{0}$ and also $m_{0} | y_{0}$ by symmetry. Thus we may write $x_{0} = n_{0}x_{1}$ and $y_{0} = m_{0}x_{1}$. Now $m_{0}n_{0}(x_{1} + y_{1}) = m_{0}x_{0} + n_{0}y_{0} = dm_{0}n_{0}$, so $x_{1} + y_{1} = d$.

Conversely, if $x_{0} = n_{0}x_{1}$ and $y_{0} = m_{0}y_{1}$ with $x_{1} + y_{1} = d$, then $(x_{0}, y_{0})$ is a solution. We incidentally showed that a nontrivial pair $(x_{0}, y_{0})$ is a solution if and only if if $x_{0} = n_{0}x_{1}$ and $y_{0} = m_{0}y_{1}$ for some nontrivial pair $(x_{1}, y_{1})$ with $x_{1} + y_{1} = d$. There are precisely $d - 1$ of them, so we must have $d - 1 + 2 = d + 1$ solutions.