Prove gcd(x,y) = gcd(x-y,y) for x > y

Question

Prove gcd(x,y) = gcd(x-y,y) for x > y Here is my work so far:

If gcd(x,y) = d, then we can denote x = ad , y = bd, so x - y = (ad - bd) = d(a - b), so (x-y) is a multiple of d, so gcd(x -y, y) = gcd(d(a - b), bd) = d, so gcd(x-y, y) = gcd(x,y).

My teacher challenged it by asking to show why gcd(d(a - b), bd) = d.

I think that gcd(d(a - b), bd) = d if gcd(a-b, b) = 1 --> gcd(a,b) = 1,

But I need some more help as to why this occurs, or if their is a simpler method of proving gcd(x,y) = gcd(x-y,y) for x > y

Answer 1

Suppose $z \mid x$ and $z \mid y$. Then write $x = az$, $y = bz$. Then $x - y = az - bz = (a - b) z$, so $z \mid x - y$. So every common factor of $x$ and $y$ is a common factor of $x - y$ and $y$.

Now suppose $z \mid x - y$ and $z \mid y$. Then write $x - y = az$, $y = bz$. Then $x = (x - y) + y = az + bz = (a + b) z$, so $z \mid x$. So every common factor of $x - y$ and $y$ is a common factor of $x$ and $y$.

Since $x, y$ and $x - y, y$ have the same set of common factors, they must have the same gcd.

Answer 2

• First prove that every divisor that $x$ and $y$ have in common is a divisor of $x-y.$
• Then prove that every divisor that $x-y$ and $y$ have in common is a divisor of $x.$

Thus the set of common divisors of $x$ and $y$ is the same as the set of common divisors of $x-y$ and $y.$