# 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?

• Do you see that the left-handside divides the righthand side? – quid Sep 1 '16 at 20:28
• Yeah, that part makes sense to me. I'm having trouble seeing how ad-bc = +-1 is relevant – kojak Sep 1 '16 at 20:42

$\forall m,n; \gcd(x,y)| (mx + ny)$

$\gcd(x,y)|(ax+by)$ and $\gcd(x,y)|(cx+dy)$

$\gcd(x,y)|\gcd(ax+by, cx+dy)$

$\gcd(ax+by, cx+dy)|(d(ax+by) - b(cx+dy))\\ \gcd(ax+by, cx+dy)|(ad - bc)x\\ \gcd(ax+by, cx+dy)|x$

similarly we can show that

$\gcd(ax+by, cx+dy)|(c(ax+by) - a(cx+dy))$ and $\gcd(ax+by, cx+dy)|y$

$\gcd(ax+by, cx+dy) | \gcd(x,y)$

if $\gcd(ax+by, cx+dy) | \gcd(x,y)$ and $\gcd(x,y)|\gcd(ax+by, cx+dy)$ then $\gcd(ax+by, cx+dy) = \gcd(x,y)$

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.

First note that LHS|RHS. (as quid said in the comments) For RHS|LHS,let $u=gcd(ax+by,cx+dy)$

Then $u | ax+by$ which implies $ku=ax+by------(1)$

for some integer $k$.

Similarly, $u|cx+dy$ which implies $lu=cx+dy-----(2)$

for some integer $l$.

Now, lets find $a(2)-c(1)$

$cku-alu=acx+bcy-acx-ady$

$(al-ck)u=(ad-bc)y$

Since $ad−bc=±1$,

$y=(al-ck)u/(ad-bc)$ which implies $y=±1(al-ck)u$

Therefore, $u|y$. A similar argument shows using $d(2)-b(1)$, $u|x$ and therefore $u|gcd(x,y)$, which is RHS|LHS. Since both sides divide each other, they are equal up to sign. But since both sides are defined positively therefore this is an equality.

It is the special case $\rm\, \Delta := {\rm det}\, A= \pm1\$ in the following

Theorem $\$ If $\rm\,(x,y)\overset{A}\mapsto (X,Y)\,$ is linear then $\: \rm\gcd(x,y)\mid \gcd(X,Y)\mid \Delta \gcd(x,y)$

Proof $\$ Inverting the linear map $\rm\,A\,$ by Cramer's Rule (multiplying by the adjugate) yields

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

Hence, by RHS system, $\rm\ n\ |\ X,Y\ \Rightarrow\ n\ |\ \Delta\:x,\:\Delta\:y\ \Rightarrow\ n\ |\ gcd(\Delta\:x,\Delta\:y)\ =\ \Delta\ gcd(x,y)\:.$
In particular $\rm\ n = \gcd(X,Y) \mid \Delta\, \gcd(x,y).\$

Further, by LHS system, $\rm\,n\mid x,y\ \Rightarrow\ n\mid X,Y\ \Rightarrow\ n\mid\gcd(X,Y).$
In particular $\rm\ n = gcd(x,y)\mid \gcd(X,Y).\ \ \$ QED

Remark $\$ See here for many special-case applications.

• What is $n$? Moreover, is there a book/pdf where I can read more about this method. – model_checker Nov 2 '16 at 6:30
• @Shrey  Above $n$ denotes any integer. I don't recall seeing this result in any textbooks. If anything else is not clear then please feel welcome to ask further questions. – Bill Dubuque Nov 2 '16 at 13:20
• Your answer seems a variant of the answer by 'quid'. If so, kindly make it more detailed. It will help me a lot. – jiten Mar 9 '18 at 13:50

Set $A=\begin{bmatrix}a&b\\c&d\end{bmatrix}$, $x'=ax+by\;$ and $\;y'=cx+dy$.

Consider the commutative diagram of linear forms: \begin{align*} \mathbf Z^2&\xrightarrow{[\mkern1.5mu x\;y\,]}\mathbf Z\\ {}^{\mathrm t\mkern-5mu}A\uparrow\enspace&\quad\!\!\nearrow_{[\mkern1.5mu x'\;y'\,]}\\[-2ex] \mathbf Z^2& \end{align*} This diagram shows the image $I'$ of the linear form $[\mkern1.5mu x'\;y'\,]$ is contained in the image $I$ of $[\mkern1.5mu x\;y\,]$.

Conversely, multiply the relation $\;[\mkern1.5mu x'\;y'\,]=\,[\mkern1.5mu x\;y\,]\,{}^{\mathrm t\mkern-5mu}A$ on the right by the comatrix $\;\operatorname{com}({}^{\mathrm t\mkern-5mu}A)={}^{\mathrm t\mkern-1.5mu}(\operatorname{com}A)$. You obtain $$[\mkern1.5mu x'\;y'\,]{\,}^{\mathrm t\mkern-1.5mu}(\operatorname{com}A)=[\mkern1.5mu x\;y\,]\,{}^{\mathrm t\mkern-5mu}A{\,}^{\mathrm t\mkern-1.5mu}(\operatorname{com}A)=[\mkern1.5mu x\;y\,]\,{}^{\mathrm t\mkern-1.5mu}((\operatorname{com}A)A)=[\mkern1.5mu x\;y\,](\det A)I=[\mkern1.5mu x\;y\,]$$ This proves $I\subset I'$, whence $I=I'$, and eventually $\gcd(x,y)=\gcd(x',y')$, since these are the positive generators of $I$, $I'$ respectively.

We can reduce to the case $$\,\gcd(x,y) = 1\,$$ by cancelling $$\,\gcd(x,y)\,$$ from both sides. Bezout's GCD identity implies that $$\,\gcd(x,y) = 1\,$$ iff it is a column in a $$2\times 2$$ matrix of determinant $$\pm1,\,$$ hence

$$\pm1\ = \ \begin{vmatrix} a & b \\ c & d\end{vmatrix}\ \begin{vmatrix} x & u \\ y & v \end{vmatrix}\ =\ \begin{vmatrix} ax+by & \bar u \\ cx+dy & \bar v \end{vmatrix} \ \Rightarrow\ \gcd(ax+by,\ cx+dy)\ =\ 1$$