# If $\gcd(x,y)=1$ and $ad-bc = 1$, why are $(ax+by)$ and $(cx+dy)$ relatively prime? [duplicate]

Possible Duplicate:
Proving two gcd's equal

Let $a,b,c,d,x,y$ be integers with $\gcd(x,y)=1$ and $$\begin{vmatrix} a & b \\ c & d \end{vmatrix} = ad-bc = 1.$$ I have come across the assertion that $(ax+by)$ and $(cx+dy)$ must be relatively prime, but I don't see why.

$gcd(x,y)=1$ means there are $C,D$ such that $$Cx+Dy=1$$

I want to find $A,B$ such that $$A(ax+by) + B(cx+dy) = 1.$$

I've tried expanding and regrouping the terms in the LHS in different ways to try to use what I've got, but I'm stuck.

-

## marked as duplicate by Bill Dubuque, Aryabhata, anon, lhf, Henning MakholmApr 14 '12 at 1:47

Exact duplicate of said question. Answers are duplicates too. – Bill Dubuque Apr 14 '12 at 1:33

In other words, given $C,D$ you want to solve the following for $A,B$.

$$\begin{pmatrix} a & c \\ b & d \end{pmatrix} \begin{pmatrix} A \\ B \end{pmatrix} = \begin{pmatrix} C \\ D \end{pmatrix}$$

Since $\det = ad-cb=1$ the inverse will have integer components. If we multiply by the inverse,

$$\begin{pmatrix} A \\ B \end{pmatrix} = \begin{pmatrix}d & -c \\ -b & a\end{pmatrix} \begin{pmatrix} C \\ D \end{pmatrix}.$$

Note this proves $\gcd(x,y)$ is invariant under the action of the special linear group $SL_2(\Bbb Z)$.

-

$$\begin{vmatrix} a & b \\ c & d \end{vmatrix} \begin{vmatrix} x \\ y \end{vmatrix}= \begin{vmatrix} ax+by\\ cx+dy \end{vmatrix}$$

Thus

$$\begin{vmatrix} x \\ y \end{vmatrix}= \begin{vmatrix} a & b \\ c & d \end{vmatrix}^{-1} \begin{vmatrix} ax+by\\ cx+dy \end{vmatrix}= \begin{vmatrix} d & -b \\ -c & a \end{vmatrix} \begin{vmatrix} ax+by\\ cx+dy \end{vmatrix}$$

Now, replace this in $Ax+By=1$ and you get your desired result.

-