Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

2 Answers

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.