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

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.

• Hint: For each $i$, let $r_i$ be the number with $0\leq r_i<n$ and $x_i-r_i$ is divisible by $n$. – Thomas Andrews Oct 5 '14 at 0:31

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

• Thanks so much again. You really helped me see that the key came down to realizing that taking the difference strips away the remainder. – user176049 Oct 5 '14 at 2:22

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

• I'm familiar with pigeonhole, but I don't understand what you mean by equivalence class. Say the integers are 7 and 2. 7 - 2 = 5, divisible by 5. How does this necessarily put 7 and 2 in the same class? – user176049 Oct 5 '14 at 0:59
• In modular arithmetic, two numbers are in the same equivalence when they have the same remainder when divided by $n$. If $n = 5$, the possible remainders are $0, 1, 2, 3, 4$. Thus, $2$ and $7$ would be in the same equivalence class $\mod 5$ since both $2$ and $7$ have remainder $2$ when divided by $5$. We write $7 \equiv 2 \pmod 5$. – N. F. Taussig Oct 5 '14 at 2:06