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

\begin{equation} (R_{6}(x), R_{8}(x)) = (a, b), \end{equation}

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

(-tikz- diagram)

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.