Show : $(m,n)=1\implies(mx+ny,mn)=(m,y)(n,x)\;\forall x,y\in\mathbb Z$.

Question

I figured the best way to go about this would be to show that $(m,y)(n,x) \mid (mx+ny,mn)$ and $(mx+ny,mn) \mid (m,y)(n,x)$. So far I've done the following:

Since $\mathbb{Z}$ is a Euclidean domain, $\exists s,t\in\mathbb Z$ s. t. $(mx+ny,mn)=(mx+ny)s +mnt = mxs+nys+mnt = (m,y)(n,x)\left(\frac{mxs+nys+mnt}{(m,y)(n,x)}\right)$. Thus, $(m,y)(n,x) \mid (mx+ny,mn)$, since $\frac{mxs+nys+mnt}{(m,y)(n,x)} \in \mathbb{Z}$.

$\exists a,b,c,d\in\mathbb Z$ s.t. $(m,y) = ma+yb\;\&\;(n,x) = nc+xd$.

Then, $(m,y)(n,x)= (ma+yb)(nc+xd)=mnac+mxad+nybc+xybd$.

From here I'm not seeing any way to show that $(mx+ny,mn) \mid (m,y)(n,x)$. If anyone could give any hints I would appreciate it, thanks!

Answer 1

A factor of $mn$ is either in $m$ or in $n$, since $(m,n)=1$. If it’s in $m$ and also in $mx+ny$ but not in $n$, then it must be in $y$, and thus also in $(m,y)$. Thus all factors in $(mx+ny,mn)$ are in $(m,y)$. Likewise for $(n,x)$. It follows that $(mx+ny,mn)\mid(m,y)$ and $(mx+ny,mn)\mid(n,x)$, and either is enough to show $(mx+ny,mn)\mid(m,y)(n,x)$.

Answer 2

By Euclid & $\,(\color{#c00}{m,n})=1\!:$ $\ \ \begin{align} \color{#0a0}{(mx\!+\!ny,m)} &=\:\! (\color{#c00}ny,\color{#c00}m) = \color{#0a0}{(y,m)}\\ (mx\!+\!ny,n)\ &= (\color{#c00}mx,\color{#c00}n) = (x,n) \end{align}$

So $\,(\underbrace{mx\!+\!ny}_{\large a},mn) = \underbrace{\color{#0a0}{(y,m)}}_{\large \color{#0a0}{(a,m)}}\underbrace{(x,n)}_{\large (a,n)}\ $ by $\ (a,m)(a,n) = (a(a,\color{#c00}{m,n}),mn) = (a,mn)$