I am trying to prove a version of the Chinese Remainder Thoerem using the pigeonhole principle.
The theorem that was provided:
If $n$ and $m$ are relatively prime, then for all integers $0 ≤a< n$ and $0 ≤ b < m,$ there is an integer solution to the equation set $x\equiv a\pmod n$ and $x\equiv b\pmod m$.
Note that those are equal signs and not congruency, but in this case, I don't think that should impact it. I started with trying to rearrange the statements to maybe make more sense of them (so it became $x-nc=a$ which became $x=a+nc$ where $c$ is whatever constant needed to satisfy the equation due to the definition of modulo), however, from here I'm stuck.
Specifically with the pigeonhole theorem, I'm unsure how to use it in this case. I was also given the hint to consider the sequence $b, b+m, b+2m, ..., b+(n-1)m,$ but unsure how to consider it.
Thanks for any help you can give.
From the hint:
$$b, b+m, b+2m,..., b+(n-1)m$$
forms a complete residue class modulo $n$. To see this, first consider the sequence
$$0,m, 2m, 3m, ..., (n-1)m$$
Since $(m,n)=1$, we have $xm \equiv ym \text{ mod n} \iff x \equiv y \text{ mod n}$, since $m$ has a mutiplicative inverse modulo $n$. Hence each of these elements in the sequence are unique. Adding $b$ does nothing more than cyclically permute the residue class.
By the pigeonhole principle, for any $0\le a < n$, we must have $b+km=a \text{ mod n}$ for some $k\in\{0,...,n-1\}$. Then $x=b+km$ satisfies the property you want.