Chinese Remainder Theorem Consequence 2

Question

The Chinese remainder theorem as stated in my textbook: If $a,b \in \Bbb Z $ such that $\gcd(a,b) = 1$ then for arbitrary $c,d \in \Bbb Z$ there exists an $x \in \Bbb Z $ with $x \equiv c\bmod a$ and $x \equiv d \bmod b$. It then gives a proof (which I understand) showing that by taking $p,q \in \Bbb Z$ such that $pa + qb = 1$ that $x \equiv pad + qbc \bmod ab$. What I do not understand is the $\bmod ab $ part of this equation? Can anyone shed some light on where this came from?

Answer 1

There was no need for introducing $\operatorname{mod}ab$ in the proof for the original statement (namely, there exists $x \in \mathbb{Z}$). Once we have $pa+qb = 1$, it easily follows that

$x = pad + qbc$ does the job, since

$x \equiv qbc \equiv c \operatorname{mod} a$ where the last congruence follows because

$pa+qb = 1 \implies qb \equiv 1 \operatorname{mod} a$. Similarly

$x \equiv d \operatorname{mod} c$.

However, it is easy to check that any $y\equiv x \operatorname{mod} ab$ also does the job, which is what the statement $x \equiv pad + qbc \operatorname{mod} ab$ means.

Note that with a little more work, it can also be shown that such an $x$ is unique $\operatorname{mod} ab$.