What is the minimum number of ordered pairs

Question

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 \equiv c \mod \;3 \;and \;b \equiv d \mod \;5$$

1. 4
2. 6
3. 16
4. 24

---

Somewhere it explained as :

order pair for (a,b) are

(0,0), (0,1), (0,2), (0,3) (0,4)
(1,0), (1,1), (1,2), (1,3) (1,4)
(2,0), (2,1), (2,2), (2,3) (2,4)

take any other combination for (c,d) that ll surely match with one of the above 15 combination.(Pigeon Hole principle) total 15+1 = 16 combination

Can you explain in formal way please?

Answer 1

Every non-negative integer is congruent to exactly one of $0,1$, and $2$ modulo $3$, and every non-negative integer is congruent to exactly one of $0,1,2,3$, and $4$ modulo $5$. Thus, there are $3$ congruence classes modulo $3$, and $5$ congruence classes modulo $5$.

Now consider an ordered pair $\langle a,b\rangle$ of non-negative integers: $a$ can be congruent to any one of $0,1$, and $2$ modulo $3$, and, independently of that, $b$ can be congruent to any one of $0,1,2,3$, and $4$ modulo $5$. In effect the pair $\langle a,b\rangle$ uses $a$ to select one item from the $3$-element ‘menu’ $0,1,2$ of congruence classes modulo $3$, and $b$ to select one item from the $5$-element ‘menu’ $0,1,2,3,4$ of congruence classes modulo $5$.

Each of the $3$ possible congruence classes for $a$ can be paired with any of the $5$ possible congruence classes for $b$, so there are $3\cdot 5=15$ possible ordered pairs of congruence classes – $15$ ways to select one item from each ‘menu’. Those $15$ possibilities are listed in your table: no matter what non-negative integers $a$ and $b$ are, reducing $a$ modulo $3$ and $b$ modulo $5$ will yield exactly one of the entries in that table. For instance, $\langle 22,108\rangle$ reduces to $\langle 1,3\rangle$, because $22\equiv1\pmod3$, and $108\equiv3\pmod5$.

If you take any two entries in your table, either they’re in different rows, in which case their first components are not congruent modulo $3$, or they’re in different columns, in which case their second components are not congruent modulo $5$. If you have $16$ (or more) ordered pairs, however, at least two of them, say $\langle a,b\rangle$ and $\langle c,d\rangle$ must reduce to the same entry in that table, say the entry $\langle i,j\rangle$. But then

$$a\equiv i\equiv c\pmod3$$

and

$$b\equiv j\equiv d\pmod5\;,$$

so $a\equiv c\pmod3$ and $b\equiv d\pmod5$, as desired.