Pigeonhole Principle about division Prove that, for any $n+1$ integers $a_{1},a_{2},....,a_{n+1}$, there exist two of the integers $a_{i}$ and $a_{j}$ with $i \neq j$, such that $a_{i} - a_{j}$ is divisible by $n$.
Please help me about this problem,I know there is lots of answers can find from Google, but I am not really understand them. I hope someone can give me more details explanation. I would really appreciate your help.
 A: You can solve the problem using modular arithmetic, or if you haven't learned that yet, just division with remainder.
Hint: try a specific example first.  (Nearly always a good idea!)  Let's say $n=4$ and your five numbers are $31,\,41,\,59,\,26,\,53$.  What remainders do you get when you divide these numbers by $4$?  Do you notice anything?  Does it help you to find two of these numbers with difference divisible by $4$?
Now try choosing your own five numbers.  Does the same thing happen?  And try some examples with $n$ other than $4$.  Does the same sort of thing always happen?  Can you see why it will happen for all the examples you haven't tried yet?
If you can do this I think you should be close to answering the question.  But remember that proofs are always hard - don't expect to have the whole thing solved in $60$ seconds.  Good luck!
A: If remainders or modular arithmetic are unfamiliar then you can prove it by induction. Suppose a counterexample exists. Wlog we may assume all $\,a_i > 0\,$ by shifting them all by a fixed amount $\,k.\,$ This preserves their differences $\,(a_i+k)-(a_j+k) = a_i-a_j,\,$ so the shifted positive $\,a_i$ remain a counterexample. Among such positive counterexamples choose one with $\rm\color{#c00}{least}$ max element $\,m.\,$ Necessarily $\,m > n\,$ (else the $\,n+1\,$ values of $\,a_i$ would lie in $\,\{1,2,\ldots,n\},\,$ so two are equal $\,a_i = a_j\,\Rightarrow\,n\mid a_i-a_j).\,$ Since $\,m>n\,$ we can replace $\,m\,$ by $\,m-n\,$ and obtain a positive counterexample with smaller max element, a $\,\rm\color{#c00}{contradiction}\,$ (here we use the fact that $\,n\mid (m-n)-a_i\iff n\mid m-a_i,\,$ so the replacement preserves the counterexample). $\ $ QED
Remark $\ $ Interpreted constructively, essentially the proofs shows that we can replace the $\,a_i\,$ by their remainders mod $\,n,\,$ i.e. the least positive value of $\,a_i + kn,\,$ which whould lead to $\,n+1\,$ distinct integers in the set $\,\{1,2,\ldots,n\}$ of cardinality $\,n\,$ (the base case of the induction), i.e. contra the Pigeonhole Principle (or equivalent).
A: To use the pigeon hole principal to prove this, you need to think about how many different remainders can you get when you divide by $n$. In the above example (when $n=4$), when you divide any number by 4 you can get exactly 4 different remainders: $0,1,2,$ or $3$.
Then you need to think about how a random set of $n+1$ numbers (in the above example, $5$ numbers), no matter how they are chosen, will force you to have at least two numbers with the same remainder when divided by $n$.
