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!

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

2 Answers 2


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

  • $\begingroup$ Could you maybe elaborate a little bit? I'm not sure I understand how the result follows $\endgroup$ Feb 5, 2020 at 13:28
  • $\begingroup$ @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. $\endgroup$
    – joriki
    Feb 5, 2020 at 13:41
  • $\begingroup$ @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, $\endgroup$ 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)$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.