With $a,\ b,\ m,\ n\in \mathbb{Z}$. Show that if ${\rm gcd}(m,n)=1$, then ${\rm gcd}(ma+nb,mn)={\rm gcd}(a,n){\rm gcd}(b,m)$

elementary-number-theorygcd-and-lcm

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.

Best Answer

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}$.

Related Question