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

Question

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

Using a little bit of algebra, I arrived at: $$x=b_2m-b_1n\tag{1}$$ and $$y=a_1n-a_2m\tag{2}$$

But then I'm at a loss. What should I consider next? I did plug in a couple of values and it holds.

Answer 1

From the condition we have that $(x,y) \mid m$ and $(x,y) \mid n$. This means that $(x,y) \mid (m,n)$. Similar reasoning for the two equations you've obtained gives us that $(m,n) \mid (x,y)$, hence $(m,n) = (x,y)$

Answer 2

Hint: $\gcd(x,y)|m$ and $\gcd(x,y)|n\Rightarrow\gcd(x,y)|\gcd(m,n)\Rightarrow\gcd(x,y)\leq \gcd(m,n).$ From the equations you derived for $x$ and $y$ you can deduce that $\gcd(m,n)|\gcd(x,y)\Rightarrow\gcd(m,n)\leq\gcd(x,y).$ Thus we have $\gcd(m,n)\leq\gcd(x,y)\leq \gcd(m,n)\Rightarrow \gcd(x,y)=\gcd(m,n).$