I'm having problems with an exercise from Apostol's Introduction to Analytic Number Theory.
Given $x$ and $y$, let $m=ax+by$, $n=cx+dy$, where $ad-bc= \pm 1$. Prove that $(m,n)=(x,y)$.
I've tried to give a proof, but I suspect it's wrong (or at least not very good). I would be very thankful for any hints/help/advice!
My proof:
We observe that since $ad-bc= \pm 1$, $ad=bc \pm 1$, and $(ad,bc)=1$.
Now, $(a,b) \mid m$ and $(c,d) \mid n$ but$$(a,b) = ((d,1)a,(c,1)b)=(ad,a,bc,b)=(ad,bc,a,b)=((ad,bc),a,b)=(1,a,b)=1.$$
Similarly, we determine $(c,d)=1$. So, $1=(a,b) \mid m$ and $1=(c,d)
> \mid n$. But $(x,y)$ also divide $m$ and $n$. Since $(x,y) \geq (a,b)=(c,d)=1$, this implies that $(x,y)=m,n$. Hence
$(m,n)=((x,y),(x,y))=(x,y)$.
Best Answer
Here is a proof. Call $z=(x,y)$ and $p=(m,n)$. The expressions of $m$ and $n$ as integer linear combinations of $x$ and $y$ show that $z$ divides $m$ and $n$ hence $z$ divides $p$ by definition of the gcd. On the other hand, $\pm x=dm-bn$ and $\pm y=cm-an$ hence the same argument used "backwards" shows that $p$ divides $\pm x$ and $\pm y$, which implies that $p$ divides $z$, end of proof.