1
$\begingroup$

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.

Can someone please help me out?

  • 0
    *Exact* duplicate of said question. Answers are duplicates too.2012-04-14

2 Answers 2

3

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)$.

1

$\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.