# $(m,n)=1$, what could $(3n-4m, 5n+m)$ be?

This is what I have so far: let's say $$d$$ is the common divisor of $$3n-4m$$ and $$5n+m$$, then $$d$$ divides $$5(3n-4m)-3(5n+m)=-23m$$ and $$3n-4m+4(5n+m)=23n$$. $$d$$ can't be a divisor of both $$m$$ and $$n$$, so 23 must divide $$d$$. But is this the greatest common divisor of $$3n-4m$$ and $$5n+m$$?

• In my understanding your conclusion does not look correct, because $d$ can divide both $m$ and $n$, and in that case it is equal to $1$. Otherwise, it divides $23$, hence it is either $1$ or $23$. Dec 6, 2018 at 23:41
• What does $(m/n)$ mean???
– bof
Dec 6, 2018 at 23:42
• I meant the greatest common divisor. Dec 6, 2018 at 23:45
• Um don't you mean $d$ must divide $23$. Not $23$ must divide $d$? Dec 7, 2018 at 1:33

If $$m=3$$ and $$n=4$$, the greatest common divisor of $$3n-4m=0$$ and $$5n+m=23$$ is $$23$$.

If $$m=1$$ and $$n=1$$, the greatest common divisor of $$3n-4m=-1$$ and $$5n+m=6$$ is $$1$$.

Your argument is good, but the conclusion is wrong: you prove that $$d$$ can be a divisor of $$23$$. Thus it is either $$1$$ or $$23$$.

• Thanks, this clears things up. Dec 6, 2018 at 23:49

By Bezout we have $$An+Bm=1$$, multiply this by $$23$$ and create some terms $$\begin{eqnarray*} 20An+4Am-4Am+3An+20Bm-15Bn+15Bn+3Bm=23. \end{eqnarray*}$$ Now factorise $$\begin{eqnarray*} (4A+3B)(m+5n) +(A-5B)(3n-4m) =23. \end{eqnarray*}$$ So if $$(4A+3B,A-5B)=1$$ then $$(m+5n,3n-4m)=23$$ and

and if $$(4A+3B,A-5B)=23$$ then $$(m+5n,3n-4m)=1$$.

You have the right idea - eliminate $$n$$ and $$m,\,$$ but your conclusion is misworded (reversed). It should state that $$23$$ must be divisible by $$d$$ (not $$23$$ must divide $$d$$) since $$\,d\mid 23m,23n\iff d\mid (23m,23n)\! =\! 23(m,n)\! =\! 23\ \ {\rm by}\ \ (m,n)=1$$

Remark  We can use linear algebra language, i.e. use Cramer's rule to solve for $$\,m,n\,$$ below

$$\qquad\qquad\qquad$$ $$\begin{eqnarray} 3\ n\, - 4\,m &\ =\ & i\\[.3em] \ 5\,n +\, 1\,m &=& j \end{eqnarray}\quad\Rightarrow\quad$$ \begin{align} \ 23\,n\ &= \ \ \ \ \ \ \, i\ +\, 4\,j \\[.3em] 23\,m\, &=\, -5\,i\ +\ 3\,j \end{align}

Thus by RHS: $$\,d\mid i,j\,\Rightarrow\, d\mid 23m,23n\,\Rightarrow\, d\mid 23\$$ as above. More generally this method yields

Theorem $$\$$ If $$\rm\,[x,y]\overset{A}\mapsto [X,Y]\,$$ is linear then $$\: \rm(x,y)\mid (X,Y)\mid \color{#90f}\Delta\, (x,y),\ \ \ \color{#90f}{\Delta := {\rm det}\, A}$$

e.g.  in OP we have $$\,\color{#90f}{\Delta =\bf 23}\,$$ so the above yields $$\ (3n\!-\!4m,5n\!+\!m)\mid\color{#90f}{\bf 23}(n,m) = 23$$
using the map $$\ [n,m]\mapsto [3n\!-\!4m,\,5n\!+\!m]\$$ i.e.

$$[n,\,m]\,\mapsto\, [n,\,m]\,\underbrace{\begin{bmatrix}3 & 5\\ -4 &1\end{bmatrix}}_{\large \det A\, =\, \color{#90f}{\bf 23}} =\, [3n\!-\!4m,\,5n\!+\!m]$$

• Thanks for explaining where I went wrong, and then providing more interesting information! Dec 7, 2018 at 1:46