# Proving two gcd's equal

I'm having problems with an exercise from Apostol's Introduction to Analytic Number Theory.

Given $x$ and $y$, let $m=ax+by$, $n=cx+dy$, where $ad-bc= \pm 1$. Prove that $(m,n)=(x,y)$.

I've tried to give a proof, but I suspect it's wrong (or at least not very good). I would be very thankful for any hints/help/advice!

My proof:

We observe that since $ad-bc= \pm 1$, $ad=bc \pm 1$, and $(ad,bc)=1$. Now, $(a,b) \mid m$ and $(c,d) \mid n$, but

$$(a,b) = ((d,1)a,(c,1)b)=(ad,a,bc,b)=(ad,bc,a,b)=((ad,bc),a,b)=(1,a,b)=1.$$

Similarly, we determine $(c,d)=1$. So, $1=(a,b) \mid m$ and $1=(c,d) > \mid n$. But $(x,y)$ also divide $m$ and $n$. Since $(x,y) \geq (a,b)=(c,d)=1$, this implies that $(x,y)=m,n$. Hence $(m,n)=((x,y),(x,y))=(x,y)$.

-
You seem to work only with gcd:s of $a,b,c,d$. The claim was about $x,y,m,n$! I'm afraid I cannot follow your thinking in the last two lines. Try first a special case like $a=2,d=b=c=1$ in which case you are to prove that $(2x+y,x+y)=(x,y)$ holds for all integers $x,y$. Alternatively you can try to directly follow the hint of my answer, but I realized after posting that you may have problems at a different spot. –  Jyrki Lahtonen Jul 19 '11 at 10:51
I second Jyrki's comment: the last two sentences of your proof don't make any sense to me. –  anon Jul 19 '11 at 10:55

Here is a proof. Call $z=(x,y)$ and $p=(m,n)$. The expressions of $m$ and $n$ as integer linear combinations of $x$ and $y$ show that $z$ divides $m$ and $n$ hence $z$ divides $p$ by definition of the gcd. On the other hand, $\pm x=dm-bn$ and $\pm y=cm-an$ hence the same argument used "backwards" shows that $p$ divides $\pm x$ and $\pm y$, which implies that $p$ divides $z$, end of proof.

-
Thanks, I got it now! –  Carolus Jul 19 '11 at 11:45

Hint: Any common factor of $x$ and $y$ clearly divides both $m$ and $n$, because if $f\mid x$ and $f\mid y$, then also $f\mid ax+by$ et cetera.

The task at hand is to prove the reverse fact: any common factor of $m$ and $n$ also divides $x$ and $y$. One way of seeing this follows from the matrix equation $$\left(\begin{array}{c}m\\n\end{array}\right)= \left(\begin{array}{cc}a&b\\c&d\end{array}\right)\left(\begin{array}{c}x\\y\end{array}\right).$$

Does anything about the given condition on $ad-bc$ help you with the inverse of the above $2\times2$ matrix?

-

First note that $(x,y)$ divides both $m$ and $n$, hence $(x,y)|(a,b)$. So it suffices to show $(a,b)|(x,y)$

Consider the matrix $T=\left(\begin{array}{cc}a & b \\ c & d\end{array}\right)$. By assumption $\det T=ad-bc=\pm 1$. Hence its inverse satisfies

$T^{-1}=\pm\left(\begin{array}{cc}d & -b \\ -c & a\end{array}\right)$.

Now by definition of $m$ and $n$ we have

$T\left(\begin{array}{c}x\\ y \end{array}\right)=\left(\begin{array}{c}m\\ n \end{array}\right)$.

Hence

$\left(\begin{array}{c}x\\ y \end{array}\right)=T^{-1}\left(\begin{array}{c}m\\ n \end{array}\right)=\left(\begin{array}{c}dm-bn\\ -cm+an \end{array}\right),$

showing that $m$ and $n$ both divide $x$ and $y$.

-

HINT $\$ (excerpted from my answer to a similar question a few months ago)

Generally, inverting a linear map by Cramer's Rule (multiplying by the adjugate) yields

$$\rm\begin{pmatrix} a & \rm b \\\\ \rm c & \rm d \end{pmatrix}\ \begin{pmatrix} x \\\\ \rm y \end{pmatrix}\ =\ \begin{pmatrix} X \\\\ \rm Y\end{pmatrix}\ \ \ \Rightarrow\ \ \ \begin{array} \rm\Delta\ x\ \ \ =\ \ \ \rm d\ X - b\ Y \\\\ \rm\Delta\ y\ =\ \rm -c\ X + a\ Y \end{array}\ ,\quad\quad \Delta\ =\ ad-bc\ \$$

Therefore $\rm\ n\ |\ X,Y\ \Rightarrow\ n\ |\ \Delta\:x,\:\Delta\:y\ \Rightarrow\ n\ |\ gcd(\Delta\:x,\Delta\:y)\ =\ \Delta\ gcd(x,y)\:.$

-

HINT $\$ Reduce to the case $\:(x,y) = 1\:$ by cancelling any gcd. Now Bezout's GCD identity implies that $\ (x,y) = 1\$ iff it is a column in a matrix of determinant $1\:.\:$ Therefore

$$(x,y) = 1 \ \Rightarrow\ 1\ = \ \begin{vmatrix} a & b \\ c & d\end{vmatrix}\ \begin{vmatrix} x & u \\ y & v \end{vmatrix}\ =\ \begin{vmatrix} a\:x+b\:y & s \\ c\:x+d\:y & t \end{vmatrix} \ \Rightarrow\ (a\:x+b\:y,\ c\:x+d\:y)\ =\ 1$$

The converse follows the same way using the inverse transformation (or by easy arithmetic).

-