I don't really know how to prove this, i suppose it must have something to do with the definition of greatest common divisor and Bézout's identity.
I looked at some other questions here and thought that i had to get to gcd(ma+nb,mn)=1 and that gcd(a,n)gcd(b,m)=1 too, but i'm not sure.
On
I find it useful when doing calculations involving $\gcd(a,n)$ (or whatever variables) to use the notation:
Let $\gcd(a,n) = d$ and let $a = a'd; a'=\frac ad$ and $n = n'd; n' = \frac nd$ and we can know that that $a'$ and $n'$ are relatively prime.
Likewise let $\gcd(b,m) = e$ and let $b = b'e$ and $m = m'e$ and $b'$ and $m'$ are relatively prime.
Thus we want to prove that $\gcd(m'a'de + n'b'de, m'n'de) = de$
.....
Now you probably have proven at some point that $\gcd(fg, hg) = g\gcd(f,h)$.
So $\gcd(m'a'de + n'b'de, m'n'de) = \gcd(m'a' + n'b', m'n')de$ and we just need to prove $\gcd(m'a' + n' b', m'n') = 1$.
....
Well, let $p$ be a prime divisor of $\gcd(m'a' + n' b', m'n')$ then $p|m'n'$ so $p|m'$ or $p|n'$. Wolog $p|m'$ so then $p|m'a' + n'b'$ so $p|n'b'$ but as $b', m'$ are relatively prime we know $p\not \mid b'$ so $p|n'$.
So $p|m'$ and $p|n'$.
But we were told $\gcd(m,n) = 1$ so there can't be any prime divisors that divide both $m',n'$.
So there are no prime divisors of $\gcd(m'a' + n' b', m'n')$. So $\gcd(m'a + n'b', m'n') = 1$.
By $\rm\color{#c00}H$ere $\color{#c00}{(m,n)\!=\!1}\Rightarrow (ma\!+\!nb,\color{#c00}{mn}) \overset{{\rm\color{#c00}H}}= (ma\!+\!nb,\color{#c00}m)(ma\!+\!nb,\color{#c00}n) = (b,m)(a,n)\ $ by
$$\begin{align}(\color{#0a0}ma+nb,\color{#0a0}m) &\overset{\rm\color{#f6f} R}= (nb,m) \overset{\rm\color{darkorange}L}= (b,m)\\[.2em] (ma+\color{#0af}nb,\ \color{#0af}n) &\overset{\rm\color{#f6f} R}= (ma,n) \overset{\rm\color{darkorange}L}= (a,n)\end{align}\qquad$$
where above we applied gcd $\rm\color{#0a0}{mod}\ \color{#0af}{reduction}$ = $\rm\color{#f6f} R,\ $ and $\ \rm\color{darkorange}L = $ Euclid's Lemma, by $\, \color{#c00}{(m,n)=1}$.