Prove that there exist two integers such that i - j is divisible by n.

Question

Here's the full question:

Prove that, for any $n + 1$ integers, $\{x_0, x_1, x_2, . . . , x_n\}$, there exist two integers $x_i$ and $x_j$ with $i \neq j$ such that $x_i − x_j$ is divisible by $n$.

Now, the integers aren't necessarily consecutive, positive, or without repeats. I've tried breaking this into cases, such as "$x_i = x_j, \dfrac{0}{n} = 0$" etc. But I don't think it's possible to exhaust the cases.

I feel like there should be an easy way to contradict this one, by saying that $x_i - x_j$ isn't divisible by $n$. But I just wasn't getting anywhere with that one.

I thought about using induction, but I would have just as hard a time proving this for $n$ integers before $n+1$ integers, so I don't think it would be possible for me to do it that way.

If anyone could help out, that would be wonderful. I'm pretty stuck here.

Answer 1

This is an application of the Pigeonhole Principle. The idea is that since there are $n$ possible remainders when an integer is divided by $n$ that at least two of the $n + 1$ integers in the set $\{x_0, x_1, \ldots, x_n\}$ must have the same remainder when divided by $n$. If they have the same remainder when divided by $n$, their difference is divisible by $n$.

The possible remainders when an integer is divided by $n$ are $0, 1, 2, \ldots, n - 1$. If you have $n$ integers, then it is possible for each of them to have a different remainder when divided by $n$. However, if you have $n + 1$ integers, at least two of them must have the same remainder when divided by $n$. Hence, in the set $\{x_0, x_1, \ldots, x_n\}$, there are two numbers $x_i$ and $x_j$, with $i \neq j$, that have the same remainder when they are divided by $n$. Thus, there exist $k, m, r \in \mathbb{N}$, with $0 \leq r \leq n - 1$, such that

\begin{align*} x_i & = kn + r\\ x_j & = mn + r \end{align*}

If we take their difference, we obtain

$$x_i - x_j = (kn + r) - (mn + r) = kn - mn = (k - m)n$$

Therefore, $x_i - x_j$ is divisible by $n$.

Answer 2

Using pigeonhole and modular arithmetic: Two integers are in the same equivalence class (mod $n$) if their difference is a multiple of $n$. There are $n$ distinct equivalence classes (mod $n$).

By the pigeonhole principle, if there are $n+1$ elements in your set, you'll run out of distinct bins, and have to put at least one number in the same bin as another number.

These two numbers, being in the same bin, have the same equivalence class, and thus their difference is a multiple of (and thus divisible by) $n$.