Given $x$ and $y$, let $m = ax + by$, $n = cx + dy$, where $ad-bc = \pm 1$. Prove that $(m, n) = (x, y)$. This is exercise 10 Chapter 1 the book Introduction 
to Analytic 
Number Theory by Tom M. Apostol. All alphabets represent integers and by $(w,z)=g$ we mean the greatest common divisor of w and z is g. What I tried:
 $m = ax + by$ and $n = cx + dy$. By solving for $x$ and $y$, and considering $ad-bc = \pm 1$ I just got that $(x,y) = (dm-bn, an-cm)$. I can't go further, please help!
 A: $m$ and $n$ are expressed as linear combinations of $x$ and $y$.
This means $(x,y) \mid m$ and $(x,y) \mid n$, which implies $(x,y) \mid (m,n)$
Treating $m = ax + by$ and $n = cx + dy$ as a system of linear equations, solving gives
$$x = \frac{dm-bn}{ad-bc} \:\: \text{and} \:\: y = \frac{an-cm}{ad-bc}$$
And, since $ad-bc = \pm 1$, then $x = \pm (dm-bn)$ and $y = \pm (an-cm)$
Applying the argument from above, we conclude $(m,n) \mid (x,y)$.
This can only happen when $|(x,y)| = |(m,n)|$, 
and since gcd's are positive $(x,y) = (m,n)$
A: The gcd of $x,y$ divides both $m$ and $n$ since they are both linear combinations of $x,y$. Hence it also divides the gcd of $m,n$.
We have $dm-bn=(ad-bc)x=\pm x$ and $-cm+an=(-bc+ad)y=\pm y$, so the gcd of $m,n$ divides both $x$ and $y$ and hence also their gcd.
Since they divide each other the two gcds must be equal.
A: Following my suggestion in the comments, suppose without loss that $(x,y)=1$ (divide both equations by this if necessary).  We have $$
\begin{bmatrix} m \\ n \end{bmatrix}  = \begin{bmatrix}a & b \\c & d \end{bmatrix}
\begin{bmatrix}x \\ y\end{bmatrix}
$$
By hypothesis the matrix $\begin{bmatrix}a & b \\c & d \end{bmatrix}$ has inverse $\begin{bmatrix}e & f \\g & h \end{bmatrix}$.  Hence 
 $$\begin{bmatrix}e & f \\g & h \end{bmatrix}
\begin{bmatrix} m \\ n \end{bmatrix}  = 
\begin{bmatrix}x \\ y\end{bmatrix}.
$$
In other words, there are integers $e,f,g,h$ such that $x=em+fn$ and $y=gm+hn$.  Now, $(m,n)$ divides both $x,y$ and so $(m,n)|(x,y)$.  But $(x,y)=1$ so $(m,n)=1$.
