If I have n+1 element, why is it true that there will always be at least two that are congruent, modulo n?

Question

As above ^; this is baffling me, I understand the intuition behind how modulus' work but it would be awesome if someone could actually explain to me how this works. Thanks in advance!

Answer 1

Let the points be $a_1,a_2,..,a_{n+1}$We can write $a_k=q_kn+r_k$ with $0\leq r_k<n$. If $r_k=r_j$ for some $j \neq k%=$ the $a_j$ is congruent to $a_k$ mod $n$. Otherwise you get $n+1$ different numbers in $\{0,1,2...,n-1\}$ which is impossible.

Answer 2

There are only $n$ different remainders ($0, 1, 2, ..., n-1$) upon division by $n$, so if you have $n+1$ integers, at least two of them will have the same remainder.

And two numbers that have the same remainder upon division by $n$, will have their difference divisible by $n$.

Answer 3

The reason is called the pigeonhole principle. It states if you have more items than containers(classifications etc) that at least two items must go in one of the containers (classifications etc).

In modular arithmetic we classify numbers by remainders. Modulo $n$ we only have $n$ remainders. Therefore, the pigeonhole principle says we will be guaranteed to have 2 numbers with the same remainder on division by $n$ if we have $n+1$ of them.