I'm having trouble figuring out how to approach this problem:

Deduce that for any $a,b,c,d\in\mathbb{Z}$ since similarly $\gcd(x,y) \mid cx + dy$ we must have that $\gcd(x,y) \mid \gcd(ax+by,cx +dy)$

Intuitively, this is my current thought process:

Since $\gcd(x,y)$ divides $cx + dy$ and $ax + by$ individually, both are multiples of the gcd, so the gcd of both equations (when looked at together) must also be a multiple of $\gcd(x,y)$

The problem is that last statement is a pretty big assumption, and I'm not sure how to prove it

  • 1
    $\begingroup$ prove that gcd $(ax+by,cx+dy)$ is of the same form. $\endgroup$ – gambler101 Sep 1 '16 at 3:16

$\gcd(x,y)$ is a common divisor of $ax+by$ and $cx+dy$, and you want to show that this means it divides their $\gcd$. Or put more simply, you want to show that $d\mid x$ and $d\mid y \implies d\mid\gcd(x,y)$.

To do this first prove Bezout's Identity, which shows that $\gcd(x,y)=ax+by$ for some $a,b\in\mathbb{Z}.$

Then, $(d\mid x\implies d\mid cx,d\mid y\implies d\mid ey)\implies d\mid cx+ey$ for any $c,e\in\mathbb{Z}$, including when $a=c$ and $b=e$, so $d\mid \gcd(x,y)$ and you're done.

| cite | improve this answer | |

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.