I am trying to solve the following problem
Let $p$ a prime number, $r$ the largest integer less than $\sqrt p$ and a number $a$ such that $p \not \mid a$. Show that there exist two pairs $(m_1,n_1)$ and $(m_2,n_2)$ such that $0 \leq m_1,n_1,m_2,n_2 \leq r$ and $m_1 + an_1$, $m_2 + an_2$ have the same remainder when divided by $p$.
My Attempt Let $A = \{m + an\ \mid 0 \leq m,n \leq \sqrt p\}$, we can see that $A$ has $(r+1)^2$ elements and then it will have the same number of remainders when divided by $p$. As $r < \sqrt p$ implies that $r^2 < p < (r+1)^2$. Since all remainders is less than $p$ by pigeonhole principle we have that there exists two pairs $(m_1,n_1)$ and $(m_2,n_2)$ such that $m_1 + an_1$, $m_2 + an_2$ have the same remainder when divided by $p$.
Note that I don't even use the fact of $p \not \mid a$ the reason is I don't know where I have to use this fact.
Thank you Guys