Dirichlet Principle

**seit** · June 6th 2011, 07:17 AM

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?

**emakarov** · June 6th 2011, 08:35 AM

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.

**Plato** · June 6th 2011, 10:51 AM

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?

Thread: Dirichlet Principle

LinkBack

Thread Tools

Display

Dirichlet Principle

Similar Math Help Forum Discussions

Dirichlet characters

Well ordering principle and the maximum principle

Dirichlet

Momentum Principle and Energy Principle Problem

Dirichlet

Search Tags