0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – conditionalMethod Oct 16 at 9:16
  • 1
    $\begingroup$ There are only $n$ possible congruence classes modulo $n$. $\endgroup$ – Mark Bennet Oct 16 at 9:21
0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.