5
$\begingroup$

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?

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

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

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is $n$? Moreover, is there a book/pdf where I can read more about this method. $\endgroup$ – model_checker Nov 2 '16 at 6:30
  • $\begingroup$ @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. $\endgroup$ – Bill Dubuque Nov 2 '16 at 13:20
  • $\begingroup$ Your answer seems a variant of the answer by 'quid'. If so, kindly make it more detailed. It will help me a lot. $\endgroup$ – jiten Mar 9 '18 at 13:50
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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