$(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$? 
 A: 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$.
A: 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$.
A: 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]$$
