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

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!

• Get $n$ boxes, one for each remainder after division by $n$. Put the $n+1$ numbers in those boxes according to which remainder they leave after division by $n$. – conditionalMethod Oct 16 at 9:16
• There are only $n$ possible congruence classes modulo $n$. – Mark Bennet Oct 16 at 9:21

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. 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.
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.
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$$.