Proving that if $ad-bc = \pm 1$, then $\gcd(x,y) = \gcd(ax +by, cx + dy)$ I'm having issues figuring out how to approach this problem:

Conclude that if $ad-bc = \pm 1$, then
  $$\gcd(x,y) = \gcd(ax +by, cx + dy)$$
  The fact that $\gcd(x,y) = \gcd(x+ky, y)$ is a very special case of this exercise

I believe there is a property that if $a = bq_1 + 0$ where 0 is r, then b divides a, and $b=\gcd(a,b)$
Is that at all relevant in this case?
 A: Let $t = \gcd(x,y)$, then it is not hard to see that $t \mid ax +by$ and $t \mid cx+dy$ and hence $t \mid \gcd(ax +by, cx + dy)$. 
Why does this work easily? Because we clearly see that $ax+by$ and $cx+dy$ can be obtained by taking a linear combination with coefficients in $\mathbb{Z}$. 
If we could obtain $x$ and $y$ as a combination of $x' = ax+by$ and $y' =cx+dy$, then we would get the divisibility relation in the other direction in the same way. 
Is this possible? 
That is can we find integers $a', b', c', d'$ such that 
$$a' x' + b'y' = x$$
$$c' x' + d'y' = y$$ 
This is indeed guaranteed by the condition imposed, and can be checked by an explicit calculation as in another answer, so I will not repeat it, yet instead point out that if you know about matrices and determinants it is direct: 
Namely setting $A = \begin{pmatrix}a & b \\ c & d  \end{pmatrix}$, 
we have 
$$A\begin{pmatrix}x \\ y  \end{pmatrix}  = \begin{pmatrix}x' \\ y'  \end{pmatrix}$$
and we seek a matrix $A'$ such that 
$$A'\begin{pmatrix}x' \\ y'  \end{pmatrix}  = \begin{pmatrix}x \\ y  \end{pmatrix}$$
and this independent of the specific value of $x,y$.
That means $A'A$ must be  the identity. In other words we need $A$ to be invertible as an integer matrix, that is its inverse is also integral. 
This is equivalent to its determinant being invertible as an integer, that is it is $\pm 1$, which is exactly the imposed condition. 
This way of looking at it also shows how to generalized to more than two numbers. 
A: $\forall m,n; \gcd(x,y)| (mx + ny)$
$\gcd(x,y)|(ax+by)$ and $\gcd(x,y)|(cx+dy)$
$\gcd(x,y)|\gcd(ax+by, cx+dy)$
$\gcd(ax+by, cx+dy)|(d(ax+by) - b(cx+dy))\\
\gcd(ax+by, cx+dy)|(ad - bc)x\\
\gcd(ax+by, cx+dy)|x$
similarly we can show that
$\gcd(ax+by, cx+dy)|(c(ax+by) - a(cx+dy))$ and $\gcd(ax+by, cx+dy)|y$
$\gcd(ax+by, cx+dy) | \gcd(x,y)$
if $\gcd(ax+by, cx+dy) | \gcd(x,y)$ and $\gcd(x,y)|\gcd(ax+by, cx+dy)$ then
$\gcd(ax+by, cx+dy) = \gcd(x,y)$
A: As in this old answer, it's a  special case  when $\rm A$ has determinant $\rm\, \Delta = \pm1\ $ in the following
Theorem $\ $ If $\rm\,[x,y]\ \smash{\overset{A}\mapsto}\ [X,Y]\,$ is linear then $\: \rm\gcd(x,y)\mid \gcd(X,Y)\mid \Delta \gcd(x,y).\,$ Therefore $\rm \,\gcd(x,y) = \gcd(X,Y)\,$ if $\rm\,\gcd(X,Y)\,$ is coprime to $\Delta\,$ (e.g. if $\,\Delta = \pm1\,$ as in OP)
Proof $\ $ Inverting the linear map $\rm\,A\,$ by Cramer's Rule (i.e. scaling by the adjugate) yields
$$\rm \begin{eqnarray}
 \rm a\ \color{#0a0}x\, +\, b\ \color{#0a0}y &=&\rm X\\[.4em]  
 \rm c\ \color{#0a0}x\, +\, d\ \color{#0a0}y &\ =\ &\rm Y\end{eqnarray}
\quad\Rightarrow\quad \begin{array}{} \rm\Delta\:\! x  \ =\ \ \ \rm d\ \color{#c00}X\, -\, b\ \color{#c00}Y \\[.4em] \rm\Delta\:\! y\ =\ \rm {-}c\ \color{#c00}X\, +\, a\ \color{#c00}Y \end{array}\ ,\quad\ \Delta\ =\ ad-bc\qquad $$
Therefore, by $\rm\color{#c00}{RHS}$ system, $\rm\ n\ |\ \color{#c00}{X,Y}\ \Rightarrow\ n\ |\ \Delta\:\!x,\:\Delta\:\!y\ \Rightarrow\ n\ |\ gcd(\Delta\:\!x,\Delta\:\!y) = \Delta\gcd(x,y),\,$ by the gcd universal property  and distributive law. $ $
In particular $\rm\ n = \gcd(X,Y) \mid \Delta\gcd(x,y).\ $
Further, $ $ by $\,\rm\color{#0a0}{LHS}\,$ system, $\rm\ n\mid \color{#0a0}{x,\,\,y}\ \Rightarrow\ n\mid X,Y\ \Rightarrow\ n\mid\gcd(X,Y)\,$ by gcd universal property.
In particular $\rm\ n = gcd(x,y)\mid \gcd(X,Y)$.
If $\rm\,\gcd(X,Y)\,$ is coprime to $\Delta$ then $\rm\,\gcd(X,Y)\mid \Delta \gcd(x,y)\Rightarrow \gcd(X,Y)\mid\gcd(x,y)\,$ by Euclid's Lemma, so the gcds are equal, by they divide each other (and $>0$ by convention) $\  $ QED

Remark $\ $ See here for many special-case applications. $ $ Below $\rm\,(m.n) :=\gcd(m,n)$.
$\rm \begin{eqnarray}
 \rm {\bf Corollary}\quad a\ \color{0a0}x\, +\, b\ \color{0a0}y &=&\rm eX\\[.4em]  
 \rm c\ \color{0a0}x\, +\, d\ \color{0a0}y &\ =\ &\rm eY\end{eqnarray},\ \ (e,\Delta)\!=\!1\!=\!(X,Y)\,\Rightarrow\, (x,y) = e$
Proof $\rm\ \ (x,y)\mid eX,eY\Rightarrow (x,y)\mid (eX,eY) = e(X,Y) = e$.
By Theorem $\rm\ e^{\phantom {|^|}}\!\!\!\mid (ax\!+\!by,cx\!+\!dy)\mid \Delta(x,y)\Rightarrow e\mid(x,y)\,$ by $\,\rm (e,\Delta) = 1$.
A: First note that LHS|RHS. (as quid said in the comments)
For RHS|LHS,let $ u=gcd(ax+by,cx+dy)$
Then $u | ax+by$ which implies $ku=ax+by------(1)$ 
for some integer $k$.
Similarly, $u|cx+dy$ which implies $lu=cx+dy-----(2)$
for some integer $l$.
Now, lets find $a(2)-c(1)$
$cku-alu=acx+bcy-acx-ady$
$(al-ck)u=(ad-bc)y$
Since $ad−bc=±1$,
$y=(al-ck)u/(ad-bc)$ which implies $ y=±1(al-ck)u$
Therefore, $u|y$. A similar argument shows using $d(2)-b(1)$, $u|x$ and therefore $u|gcd(x,y)$, which is RHS|LHS. Since both sides divide each other, they are equal up to sign. But since both sides are defined positively therefore this is an equality.
A: Set $A=\begin{bmatrix}a&b\\c&d\end{bmatrix}$, $x'=ax+by\;$ and $\;y'=cx+dy$. 
Consider the commutative diagram of linear forms: 
\begin{align*}
\mathbf Z^2&\xrightarrow{[\mkern1.5mu x\;y\,]}\mathbf Z\\
{}^{\mathrm t\mkern-5mu}A\uparrow\enspace&\quad\!\!\nearrow_{[\mkern1.5mu x'\;y'\,]}\\[-2ex]
\mathbf Z^2&
\end{align*}
This diagram shows the image $I'$ of the linear form $[\mkern1.5mu x'\;y'\,]$ is contained in the image $I$ of $[\mkern1.5mu x\;y\,]$.
Conversely, multiply the relation $\;[\mkern1.5mu x'\;y'\,]=\,[\mkern1.5mu x\;y\,]\,{}^{\mathrm t\mkern-5mu}A$ on the right by the comatrix $\;\operatorname{com}({}^{\mathrm t\mkern-5mu}A)={}^{\mathrm t\mkern-1.5mu}(\operatorname{com}A)$. You obtain
$$[\mkern1.5mu x'\;y'\,]{\,}^{\mathrm t\mkern-1.5mu}(\operatorname{com}A)=[\mkern1.5mu x\;y\,]\,{}^{\mathrm t\mkern-5mu}A{\,}^{\mathrm t\mkern-1.5mu}(\operatorname{com}A)=[\mkern1.5mu x\;y\,]\,{}^{\mathrm t\mkern-1.5mu}((\operatorname{com}A)A)=[\mkern1.5mu x\;y\,](\det A)I=[\mkern1.5mu x\;y\,]$$
This proves $I\subset I'$, whence $I=I'$, and eventually $\gcd(x,y)=\gcd(x',y')$, since these are the positive generators of $I$, $I'$ respectively.
A: We can reduce to the case $\,\gcd(x,y) = 1\,$ by cancelling $\,\gcd(x,y)\,$ from both sides. Bezout's GCD identity implies that $\,\gcd(x,y) = 1\, $ iff it is a column in a $2\times 2$ matrix of determinant $\pm1,\,$ hence
$$  \pm1\ = \ \begin{vmatrix} a & b \\ c & d\end{vmatrix}\ \begin{vmatrix} x & u \\ y & v \end{vmatrix}\ =\ \begin{vmatrix} ax+by & \bar u \\ cx+dy & \bar v \end{vmatrix} \ \Rightarrow\ \gcd(ax+by,\ cx+dy)\ =\ 1$$
