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

Printable View

- Jun 6th 2011, 07:17 AMseitDirichlet Principle
How many pairs of integers (a,b) are necessary to make sure that for two of them, say and it is the case that mod 5 = mod 5 and mod 5 = mod 5?

- Jun 6th 2011, 08:35 AMemakarov
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 and it is the case that and ?

Dirichlet (or Pigeonhole) Principle talks about pigeons and holes. I suggest considering pairs where as pigeons and pairs where and as holes. A pigeon is in the hole if and . 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. - Jun 6th 2011, 10:51 AMPlato