pigeonhole principle problem 3

Question

Prove: For every group of 1009 positive integers, there exist 2 integers of that group, that their sum or difference divide with 2014 without residue.

where do I start?

Answer 1

The remainders when $2014$ divides a number is given by the set $$S = \{0\} \bigcup \{1007\}\displaystyle\bigcup_{r=1}^{1006}\{r,2014-r\} = \bigcup_{k=0}^{1007} S_k$$ where $S$ is written as a union of $1008$ mutually disjoint sets, where $S_0=\{0\}$, $S_{1007} = \{1007\}$ and $S_k = \{k,2014-k\}$. Since there are $1009$ numbers there exists two numbers say $a_1,a_2$ whose remainders fall in the same of the $1008$ sets say some $S_k$. If the remainders of $a_1,a_2$ are the same, then their difference is divisible by $2014$. Else if the remainders are different, then their sum is divisible by $2014$.

Answer 2

Hint: Think about the possible residues when dividing the integers by 2014 (i.e. 0 to 2013). When do two of these residues sum to 0? When do two of these residues lead to a difference of 0? How many different residues could you have?

Let $N$ be the set of the residues of the 1009 positive integers modulo 2014. Suppose there are two integers with equal residues, i.e., $n_1 \equiv n_2$ mod $2014$. Then $n_1-n_2\equiv0$ mod $2014$. Then assume no two numbers have equal residues (or any number has residue 0). Assume that for any $n_1, n_2\in N$, it is not the case that $n_1+n_2\equiv 0$ mod $2014$. Then for each $n\in N$, its unique inverse mod 2014 is not in $N$. Since there are 1009 unique residues in $N$, there must be 1009 residues not included. However $1009 + 1009 = 2018 > 2014$. This implies that the number of residues of 2014 is greater than 2014, which is a contradiction.