Show that there exists $i$ and $j$ ($i \neq j)$ such that $a_i \equiv a_j \pmod m$

Question

Let $m$ be a natural number. Show that if we have a list $a_1, a_2, \dots, a_{m+1}$ of $(m+1)$ numbers, then at least two of these numbers must be congruent modulo $m$.
Or, in other words: Show that there exists $i$ and $j$ ($i \neq j)$ such that $a_i \equiv a_j \pmod m$.

Now, if $a_i \equiv a_j \pmod m$, then $m \mid (a_i- a_j)$ such that $a_i - a_j = qm$ for an integer $q$. But how to I prove the $\underline{existense}$ of such numbers $a_i$ and $a_j$? I've made an attempt underneath, but it feels like it might be too simple:

If $m$ is even, $m \mid (a_i - a_j)$ holds if $a_i$ and $a_j$ is $\underline{both}$ even or $\underline{both}$ odd. If $m$ is odd, $m \mid (a_i - a_j)$ holds if one of $a_i$ and $a_j$ is even while the other one is odd. Thus, we can always find an $a_i$ and $a_j$ which fulfills $m \mid (a_i-a_j) \Rightarrow a_i = a_j \pmod m$.

Answer 1

Every integer, divided with m, leaves a remainder that belongs in {0,1,...,m-1}, which are exactly m numbers. Now that you have m+1 integers, at least two of them will have the same remainder (as Carl suggested). As a result, at least two of m+1 numbers will be congruent modulo m.

Answer 2

Hint: Try using the Piegonhole Principle on values of $a_i\mod m$.