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

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!

• may I ask where you found that task? Maybe it would be useful for me as a student as well.(: Feb 5, 2020 at 11:53
• @VerkhovtsevaKatya It's an exercise in LeVeque's "Fundamentals of Number Theory". Feb 5, 2020 at 12:05
• thank you very much! Feb 5, 2020 at 12:06
• Is this your original problem:books.google.hr/… ? Feb 5, 2020 at 12:18
• @VerkhovtsevaKatya No, it's LeVeque "Fundamentals of Number Theory" (1977) Section 2.1 Exercise 5. Feb 5, 2020 at 12:20

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

• Could you maybe elaborate a little bit? I'm not sure I understand how the result follows Feb 5, 2020 at 13:28
• @BalsamicVinegar: By "result" I meant just the half that you hadn't proved yet. I've edited the answer to make that more explicit. If it's still unclear, please state specifically which part isn't clear to you. Feb 5, 2020 at 13:41
• @BalsamicVinegar Be aware that if you wish to make the above answer rigorous then you need to rigorously justify the various claims about "factors being in" etc, e.g. by using existence and uniqueness of prime factorizations, or related results such as Euclid's Lemma, or gcd poperties, Feb 5, 2020 at 14:10

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)$$

• The first line uses basic Euclid gcd laws $\rm\,(a,b) = (\bar a,\,b)\ \ if\ \ a\equiv \bar a\pmod{b}\ \ \$ Feb 5, 2020 at 14:22
• and also Euclid's Lemma $\rm\,(ad,b) = (d,b)\,\$ if $\,\rm\ (d,b) = 1\ \$ Feb 5, 2020 at 14:26
• The last line uses basic gcd "polynomial" arithmetic, i.e. the gcd associative, commutative and distributive laws. Feb 5, 2020 at 14:30
• Alternatively homogeneous reduce to the case $\ (m,y)=1=(n,x)\ \ \$ by cancelling $\,(m,y)(n,x)\$ Feb 5, 2020 at 14:41