Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 3 down vote accepted

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$.

share|cite|improve this answer
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)$

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.