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?

Solution 1:

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.