# A calculus of the absurd

##### 19.2.4 The Chinese remainder theorem (and related problems)
• Example 19.2.3 Consider the function $$f : \mathbb {Z}_{48} \to \mathbb {Z}_{6} \times \mathbb {Z}_{8}$$, where $$f$$ is defined by $$f(x) = \big (R_{6}(x), R_{8}(x)\big )$$.

Prove or disprove whether $$f$$ is surjective.

This statement is false, and we can prove it like this; first note that for $$f$$ to be surjective it must be true that for every $$(a, b) \in \mathbb {Z}_{6} \times \mathbb {Z}_{8}$$ there exists some $$x$$ such that

$$(R_{6}(x), R_{8}(x)) = (a, b),$$

which is equivalent to the system of congruence equations

\begin{align} & x \equiv _{6} a \\ & x \equiv _{8} b \end{align}

I found it helpful to draw a number line here, e.g. something like this

Thinking about some values for $$a$$ and $$b$$, to me at least, the problematic values will be those that are close to $$6$$ and $$8$$ (or multiples therefore). If we think about, for example, numbers which are divisible by $$6$$, but one bigger than $$8$$ or a multiple of $$8$$ (i.e. divisible by $$8$$ with remainder $$1$$), we encounter a problem, which is this; for the specific values $$a = 0$$ and $$b = 1$$ we are trying to solve the system of modular equations

\begin{align} & x \equiv _{6} 0 \implies \text { x is even} \\ & x \equiv _{8} 1 \implies \text { x is odd} \\ \end{align}

But there are no numbers which are both odd and even, so there exists no $$x$$ such that $$f(x) = (0, 1)$$, i.e. $$f$$ cannot be surjective.