Proving that these terms have no common factors

Question

If $m = a_1x + b_1y$ , $n = a_2x + b_2y$ , $a_1b_2 - a_2b_1 = 1$ then prove that $\gcd (m,n) = \gcd (x, y)$

My attempt

Let $c = \gcd (x,y)$ and $d = \gcd (m,n)$ then $c \mid d$

$\frac{d}{c} = \gcd (a_1k + b_1l, a_2k + b_2l) = \gcd \big(k(a_1 + a_2) + l(b_1 + b_2) , a_2k + b_2l \big)$ where $k = \frac{x}{c}$ and $l = \ \frac{y}{c}$

Two observations at this point are that $ \gcd (k, l) = 1$ and $\gcd (a_1 + a_2, a_2) = \gcd (b_1 + b_2, b_2) = 1$

At this point my proof will be complete if I can prove that $\frac{d}{c} = 1$ and hence $d = c$. Unfortunately I don't know how to to do this, so I would appreciate any help.

Update: I thank you all for your answers, although admittedly I don't have enough experience to understand things like Cramer's rule (I guess I'll come back to it once I learn linear algebra).

Answer 1

Let $d$ divide $m$ and $n$. Then $d$ divides $a_2m-a_1n$, which is $(a_2b_1-a_1b_2)y$, so $d$ divides $y$, but also $b_2m-b_1n=(a_1b_2-a_2b_1)x$, so, $x$. So, any common divisor of $m$ and $n$ is a common divisor of $x$ and $y$. But clearly, any common divisor of $x$ and $y$ divides both $m$ and $n$, and we're done.

Answer 2

One may easily solve the system by Cramer's rule to get $$x=mb_2-nb_1\text{ and }y=na_1-ma_2.$$ From here all common divisors of $n$ and $m$ are divisors of $x$ and $ y$ as well.

Answer 3

It is the special case of the following when the determinant $\,\Delta = 1.$

Lemma $\ $ If $\rm\,(x,y)\overset{A}\mapsto (X,Y)\,$ is linear then $\: \rm\gcd(x,y)\mid \gcd(X,Y)\mid \Delta \gcd(x,y),\,\ \Delta = \det A$

Proof $\ $ Inverting the linear map $\rm\,A\,$ by Cramer's Rule (multiplying by the adjugate) yields

$$\rm \begin{eqnarray} a\ x\, +\, b\ y &=&\rm X\\[.3em] \rm c\ x\, +\, d\ y &\ =\ &\rm Y\end{eqnarray} \quad\Rightarrow\quad \begin{array} \rm\Delta\ x\ \ \ =\ \ \ \rm d\ X\, -\, b\ Y \\[.3em]\rm\Delta\ y\ =\ \rm -c\ X\, +\, a\ Y \end{array}\ ,\quad\ \Delta\ =\ ad-bc\qquad $$

Hence, by RHS system, $\rm\ n\ |\ X,Y\ \Rightarrow\ n\ |\ \Delta\:x,\:\Delta\:y\ \Rightarrow\ n\ |\ gcd(\Delta\:x,\Delta\:y)\ =\ \Delta\ gcd(x,y).$
In particular $\rm\ n = \gcd(X,Y) \mid \Delta\, \gcd(x,y). $

Further, by LHS system $\rm\,n\mid x,y\ \Rightarrow\ n\mid X,Y\ \Rightarrow\ n\mid\gcd(X,Y).$
In particular $\rm\ n = gcd(x,y)\mid \gcd(X,Y).\ \ \ $ QED

Answer 4

Let $z = \frac{d}{c} = (a_1k + b_1l \:, \: a_2k + b_2l)$

Then $z \mid b_2(a_1k + b_1l) \:,\: b_1(a_2k + b_2l)$

$\therefore z \mid b_2(a_1k + b_1l) - b_1(a_2k + b_2l) = (a_1b_2-a_2b_1)k = k$

Analogously we get $z \mid l \:$, However $(k,l) = 1 \: \therefore z = 1 \:$ and $d = c$