If GCD of x and y is G then GCD of x and x+y is also G. but how to prove it?

Question

If GCD of x and y is G then GCD of x and x+y is also G but how to prove it?

Answer 1

$$gcd(x,y)=G \Rightarrow G \mid x \text{ and } G \mid y$$

Then $G$ divides also any linear combination of $x$ and $y$, so it divides also their sum:

$G \mid x+y$

Therefore, a common divisor of $x$ and $x+y$ is $G$.

It is left to show that this divisor is the GREATEST common divisor.

We suppose that the greatest common divisor is $D>G$.

$D$ divides $x$ and $x+y$. So $D$ divides also any linear combination of $x$ and $x+y$, so it divides also their difference: $D \mid x+y -x \Rightarrow D \mid y$

That means that $D$ is a common divisor of $x$ and $y$.

Since $G$ is the greatest divisor of $x$ and $y$, it must be $D \leq G$, a contradiction.

Therefore, there is no other common divisor of $x$ and $x+y$ that is greater than $G$. So $gcd(x,x+y)=G$.

Answer 2

Hint $\ $ If $\,d\mid x\,$ then $\,d\mid x\!+\!y\iff d\mid y.\,$ Thus $\,x,\,y\,$ and $\,x,\,x\!+\!y\,$ have the same set $\,S\,$ of common divisors $\,d,\,$ hence they have the same greatest common divisor $(= \max S).$

Answer 3

Suppose $\gcd(x, y) = d$ then $d|x$ and $d|y$, it follows that

$$x = dk_1, k_1 \in \mathbb{Z}\\ y=dk_2, k_2 \in \mathbb{Z}$$

Now, if $\gcd(x, x+y) = e$ then $e | x$ and $e|x+y$, it follows $$e|dk_1+dk_2\\ e|d(k_1 + k_2)$$

Thus, $e|d$. Since $\gcd(x, x+y) = e \implies xl_1 + (x+y)l_2 = e$ and $d|x$ and $d|x+y$, $d|e$ therefore $d=e$.

Answer 4

lat $u= (x,y)$ and $v=(x,x+y)$ $$ (a) $$ $$ \exists m,n \in \mathbb{Z}.mx+ny = u $$ so $$ (m-n)x+n(x+y)=u $$ implying $$ v|u $$ $$ (b) $$ $$ \exists m',n' \in \mathbb{Z}.m'x+n'(x+y) =v $$ so $$ (m'+n')x + n'y = v $$ implying $$ u|v $$