Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

3 Answers

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|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
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.