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

- June 6th 2011, 08: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?

- June 6th 2011, 09: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. - June 6th 2011, 11:51 AMPlato