Pigeon-Hole Problem

Question

Let $p$ and $q$ be two positive integers so that the largest common divisor of $p$ and $q$ is 1. Prove that for any non-negative integers $s\leq p-1$ and $t\leq q-1$, there exists a non-negative integer $m\leq pq$ so that if we divide $m$ by $p$, the remainder is $s$, and if we divide $m$ by $q$, the remainder is $t$.

Answer 1

We define $pq$ pigeonholes, specifically all ordered pairs of integers $(i,j)$ where $0\le i< p$ and $0\le j< q$.

Given $m\in \mathbb{Z}$, we assign it to pigeonhole $(i,j)$ based on $m\equiv i\pmod{p}$ and $m\equiv j\pmod{q}$. This is well-defined, i.e. there is exactly one pigeonhole for each $m$.

Now, suppose $m,m'$ both get sent to the same pigeonhole. Then $(m-m')\equiv 0\pmod{p}$ and $(m-m')\equiv 0\pmod{q}$. Hence $p|(m-m')$ and also $q|(m-m')$, so $pq|(m-m')$, and in particular either $m=m'$ or $|m-m'|\ge pq$.

From this observation, the integers $\{1,2,\ldots, pq\}$ all must get mapped to different pigeonholes, since no two are within $pq$ of each other. Since there are $pq$ pigeonholes, each pigeonhole must have received exactly one pigeon, including the desired $(s,t)$.