application of pigeonhole principle

It is given 13 integers (some of them may be the same). Use pigeonhole principle to prove that there exist i and j with such that

is divisible by 13

for example,

is divisible by 13.

(Hint:consider the following 13 integers

.

.

.

and their remainder when divided by 13)

Re: application of pigeonhole principle

Quote:

Originally Posted by

**maoro** It is given 13 integers

(some of them may be the same). Use pigeonhole principle to prove that there exist i and j with

such that

[CENTER]

is divisible by 13

[LEFT]for example,

is divisible by 13.

(Hint:consider the following 13 integers

The idea behind this proof is that if two numbers have the same remainder when divided by 13 then there difference is divisible by 13.

Re: application of pigeonhole principle

But how this question is related to the pigeonhole principle?

Re: application of pigeonhole principle

Quote:

Originally Posted by

**maoro** But how this question is related to the pigeonhole principle?

**Of course**, we use the pigeonhole principle.

The reminders of the of the when divided by 13 are the the pigeonholes. The are the pigeons.

Re: application of pigeonhole principle

I got you mean.

Suppose is 14,then its remainder is 1 when is divided by 13

there is one pigeonhole containing more than 1 pigeon.

Re: application of pigeonhole principle

But how about if all of is not divisible by 13?

Re: application of pigeonhole principle

Quote:

Originally Posted by

**maoro** But how about if all of

is not divisible by 13?

That means the zero pigeonhole some so it is divisible by 13.