3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$
    – Gibbs
    Dec 6, 2018 at 23:41
  • $\begingroup$ What does $(m/n)$ mean??? $\endgroup$
    – bof
    Dec 6, 2018 at 23:42
  • $\begingroup$ I meant the greatest common divisor. $\endgroup$
    – Lowkey
    Dec 6, 2018 at 23:45
  • $\begingroup$ Um don't you mean $d$ must divide $23$. Not $23$ must divide $d$? $\endgroup$
    – fleablood
    Dec 7, 2018 at 1:33

3 Answers 3

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks, this clears things up. $\endgroup$
    – Lowkey
    Dec 6, 2018 at 23:49
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks for explaining where I went wrong, and then providing more interesting information! $\endgroup$
    – Lowkey
    Dec 7, 2018 at 1:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .