number of ordered pairs to get a = c mod 3 and b = d mod 5 What is the minimum number of ordered pairs of non-negative numbers that
should be chosen to ensure that there are two pairs (a,b) and (c,d) in the chosen
set such that
a = c mod 3 and b = d mod 5. 
This was asked in GATE 2005. Here they haven't mentioned any constraints on the ordered pairs. I don't have any clue how to approach this problem. Any help will be greatly appreciated. 
 A: We show that $16$ pairs are enough, but $15$ pairs need not be. 
If we have $16$ or more pairs, there are at least $6$ pairs whose first entries are congruent to each other modulo $3$.  This is because the first entry of any pair is congruent to one of $0$, $1$, or $2$ modulo $3$. If there were $\le 5$ of each type, then the number of pairs would be $\le (3)(5)=15$.
And since there are at least $6$ such pairs, $2$ of them at least have their second entries congruent modulo $5$.
To show that $15$ pairs are not enough, consider the pairs $(0,0)$, $(0,1)$, $(0,2)$, $(0,3)$, $(0,4)$, and $(1,0)$, $(1,1)$, $(1,2)$, $(1,3)$, $(1,4)$, and $(2,0)$, $(2,1)$, $(2,2)$, $(2,3)$, $(2,4)$. 
A: Hint $\ $ By CRT, the map $\,(j,k)\mapsto (j\ {\rm mod}\ 3,\ k\ {\rm mod}\ 5)\,$ is not $1$-$1$ if its domain has size $> 15$
A: This is an application of the pigeonhole principle. Every pair $(x,y)$ represents a pair of congruence classes in $\def\Z{\Bbb Z}\Z/3\Z \times\Z/5\Z$, and the question is how many pairs must be chosen to ensure that a same pair of congruence classes is attained twice. There are $\#(\Z/3\Z \times\Z/5\Z)=3\times5=15$ different such pairs of congruence classes, and the pigeonhole principle says that in whatever way $16$ pairs $(x,y)$ are chosen, two of them are bound to occupy the same pair of congruence classes. And on the other hand with only $15$ pairs $(x,y)$, it would clearly be possible to occupy every one of the $15$ pairs of congruence classes exactly once.
