# GCD logical problem

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

• prove that gcd $(ax+by,cx+dy)$ is of the same form. – 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.