Mappings Between Residue Classes

Theorem

Let $\left[\!\left[{a}\right]\!\right]_m$ be the residue class of $a$ (modulo $m$).

Let $\phi: \Z_m \to \Z_n$ be a mapping given by $\phi \left({\left[\!\left[{x}\right]\!\right]_m}\right) = \left[\!\left[{x}\right]\!\right]_n$.

Then $\phi$ is well defined iff $m$ is a divisor of $n$.

Proof

For $\phi$ to be well defined, we require that:

$\forall x, y \in \Z_m: \left[\!\left[{x}\right]\!\right]_m = \left[\!\left[{y}\right]\!\right]_m \implies \phi \left({\left[\!\left[{x}\right]\!\right]_m}\right) = \phi \left({\left[\!\left[{y}\right]\!\right]_m}\right)$

Now $\left[\!\left[{x}\right]\!\right]_m = \left[\!\left[{y}\right]\!\right]_m \implies x - y \backslash m$.

For $\phi \left({\left[\!\left[{x}\right]\!\right]_m}\right) = \phi \left({\left[\!\left[{y}\right]\!\right]_m}\right)$ we require that $\left[\!\left[{x}\right]\!\right]_n = \left[\!\left[{y}\right]\!\right]_n \implies x - y \backslash n$.

Thus $\phi$ is well defined iff $x - y \backslash m \implies x - y \backslash n$

That is, iff $m \backslash n$.

$\blacksquare$

Sources

• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 19 \alpha$