$S \subset \mathbb{Z}$ where $|S|=n$ and $n \ge 3$. Show $\exists \ x ,y \in S$ distinct with $x-y \equiv 0 \mod n-1$

Question

Take some subset $S \subset \mathbb{Z}$ where $|S|=n$ and $n \ge 3$. Show $\exists \ x ,y \in S$ distinct with $x-y \equiv 0 \mod n-1$.

Let $A = \{a_i\}_{i=1}^{n}$

First case (all elements are congruent to $0 \mod n-1$ )

If $a_i \equiv 0 \mod n-1 \quad \forall i \in (1,n)$, then $a_i - a_j \equiv 0 \mod n-1 \quad \forall i \neq j , (i,j) \in (1,n) \times (1,n)$.

Second case (one element is congruent to $0 \mod n-1$ )

If $\exists \ ! \ a_i \ | \ a_i \equiv 0 \mod n-1 $, then $\exists \ a_j , a_k \ | \ a_j \not\equiv 0 \mod n-1 $ and $a_k \not\equiv 0 \mod n-1$ for $j\neq k$.

But here I am stuck because $a_i - (a_j \lor a_k) \not\equiv 0 \mod n-1$ and also, $a_j -a_k \not\equiv 0 \mod n-1$, suggesting that my idea is fundamentally wrong or I am missing some ingredient for this proof. Indeed, for instance let $a_i = 6$, $6 \equiv 0 \mod 3$, let $a_j = 4$, $4 \equiv 1 \mod 3$ and let $a_k = 5$ ,$5 \equiv 2 \mod 3$, then none of $a_i-a_j$ or $a_j-a_k$ or $a_i - a_k$ are congruent to $0 \mod 3$

I feel like I am on the right track by separating in possible cases ,but the inconsistency outlined above suggests that my approach is erroneous and I have no other ideas on how to solve this problem, does anyone have any hint on how to solve this problem ?

Answer 1

For each $x \in S$, we have $n-1$ possibilities: $$x \equiv 0 \pmod{n-1}, \ x \equiv 1 \pmod{n-1}, \ldots, \ x \equiv n-2 \pmod{n-1}.$$ Since $S$ has $n$ elements, the pigeonhole principle implies that at least two elements of $S$, call them $x_1$ and $x_2$, satisfy $x_1 \equiv a \pmod{n-1}$ and $x_2 \equiv a \pmod{n-1}$, where $a \in \{0,\ldots,n-2\}$. This implies $x_1 \equiv x_2 \pmod{n-1}$.

Answer 2

Note that $x_i \bmod {n-1}$ can only take on at most $n-1$ distinct values. But there are $n$ different $x_i$, so it must be the case that at least two of them are the same; i.e., $x_i \equiv x_j \pmod {n-1}$ with $i \neq j$. But then $x_i - x_j \equiv 0 \pmod {n-1}$.