# Math Help - Dirichlet Principle

1. ## Dirichlet Principle

How many pairs of integers (a,b) are necessary to make sure that for two of them, say $({a_1},{b_1})$ and $({a_2},{b_2})$ it is the case that ${a_1}$ mod 5 = ${a_2}$ mod 5 and ${b_1}$ mod 5 = ${b_2}$ mod 5?

2. OK, using Google Translate, I guess the question is the following.

How many pairs of integers (a, b) are necessary to make sure that for two of them, say $(a_1,b_1)$ and $(a_2,b_2)$ it is the case that $a_1\equiv a_2\pmod{5}$ and $b_1\equiv b_2\pmod{5}$?

Dirichlet (or Pigeonhole) Principle talks about pigeons and holes. I suggest considering pairs $(a, b)$ where $a,b\in\mathbb{Z}$ as pigeons and pairs $(x, y)$ where $x,y\in\mathbb{Z}$ and $0\le x, y < 5$ as holes. A pigeon $(a, b)$ is in the hole $(x, y)$ if $a\equiv x\pmod{5}$ and $b\equiv y\pmod{5}$. You have to check that having two pigeons in one hole corresponds to the condition in the problem statement, as well as to find out the number of holes.

3. Originally Posted by seit
How many pairs of integers (a,b) are necessary to make sure that for two of them, say $({a_1},{b_1})$ and $({a_2},{b_2})$ it is the case that ${a_1}$ mod 5 = ${a_2}$ mod 5 and ${b_1}$ mod 5 = ${b_2}$ mod 5?
Let $\mathcal{L}=\{0,1,2,3,4\}$ residues mod 5.
Use the pairs in $\mathcal{L}\times\mathcal{L}$ to label 'pigeon-holes".
So we would put the pair $(15,-3)$ into the hole with label $(0,2)$.

How is this question finished?