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.
On
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$.
On
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).
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!