# HCF/LCM problem

Find the greatest number that will divide $x$, $y$ and $z$ leaving the same remainder in each case.

Now the solution for this is obtained by finding the HCF of $(x – y)$, $(y – z)$ and $(z – x)$.

Can you tell me why is that?

-
Two answers appear below, one with two up-votes, and I'm the only person who's up-voted the question so far. –  Michael Hardy Jul 3 '12 at 22:51
It's worth noting that you only have to consider any two of $x-y$, $y-z$ and $x-z$. The GCD of any pair of these quantities will be equal to the GCD of all three. –  user22805 Jul 4 '12 at 4:45

HINT: $x,y$ have the same reminder when divided by $d$ if and only if $d$ divides $x-y$.

Once you prove this, the claim follows immediately observing that $x,y,z$ have the same reminder when divided by $d$ if and only if all three pair, $x,y$; $x,z$ and $y,z$ have the same remainder when divided by $d$; if and only if $d$ divides $x-y, x-z, y-z$.

-
And you can omit one of the three final expressions: for instance $d$ dividing $x-y$ and $y-z$ implies it divides $x-z$. –  Marc van Leeuwen Jul 10 '12 at 13:27

Hint $\rm\ mod\ d\!:\ x\equiv y\equiv z\iff d\:|\:x\!-\!y,\,y\!-\!z,\,z\!-\!x\iff d\:|\:gcd(x\!-\!y,y\!-\!z,z\!-\!x)$

-

Suppose $a$ is such that $x = am+r$, $y=an+r$, $z=ap+r$, $0\leq r\lt a$. Then $x-y = a(n-m)$, $x-z = a(m-p)$, and $y-z = a(n-p)$. So $a$ divides $x-y$, $x-z$, and $y-z$, hence it divides the gcd of $x-y$, $x-z$, and $y-z$.

Conversely, suppose that $b$ divides the gcd of $x-y$, $x-z$, and $y-z$. Then $b$ divides $x-y$, hence the remainder of dividing $x$ and $y$ by $b$ is the same; and similarly, the remainer of dividing $x$ and $z$ by $b$; and of dividing $y$ and $z$ by $b$, is the same.

Thus, an integer leaves the same remainder when dividing $x$, $y$, and $z$, if and only if it divides $\gcd(x-y,y-z,z-x)$.

In particular, the largest such number is $\gcd(x-y,y-z,z-x)$ itself.

-