0
$\begingroup$

I am looking at the following number theory problem: I am given any $m+2$ integers, and must show there exist two of them whose sum (or difference) is divisible by $2m$.

My first observation was that if any two of these integers are equal, their difference is 0 and hence trivially divisible by $2m$. Moreover, I take that for any two distinct integers, their difference will be divisible by $2m$ iff they have the same remainder (when divided by $2m$).

Then it should follow that given the proposition we wish to show, if the remainders of the $m+2$ integers are distinct, there exist two numbers whose sum (but not difference) is divisible by $2m$.

So to restate the problem, from a set of $m+2$ integers each with distinct remainders, how can I show there are two whose sum is divisible by $2m$?

$\endgroup$
0
$\begingroup$

If you look at your set of $m+2$ integers mod $2m$, you have only $2m$ distinct possible numbers. As you pointed out, if any are equal then their difference will be $0$. If the numbers are all distinct, then you can only have m numbers that won't add to $0$ mod $2m$ since $(2m - x) + x = 0 $ $($mod $2m)$ since every number x where $0 \le x \le m-1$ there is a corresponding number of the form $(2m - x)$ where $m \le (2m-x) \le 2m$. From there you can say that that if there are more than $m$, (such as $m+2$) then there are two that add up to $0$ mod $2m$.

Showing that this works with a difference after showing it works with a sum is pretty easy, just show that there is a number of the form $(2m - x)$ mod $2m$ that is the negative of one of the numbers in your set.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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