Operations on Congruence Classes

We have defined the set of congruence classes modulo $n$ as ${\mathbb{Z}}_n=\{[a]\mid a\in \mathbb{Z}\}$, where $[a]=\{a+kn\mid k\in \mathbb{Z}\}$ is the congruence class of $a$ modulo $n$. In this note, we will define operations on congruence classes, and we will see how these operations are well-defined and consistent with the operations on integers.

The key idea is we have the quotient map:

$$\begin{array}{rl}\mathbb{Z}& \to {\mathbb{Z}}_n\\ a& \mapsto [a].\end{array}$$

And we already have the multiplication and addition operations on integers. We will see these operations can descent to the operations on congruence classes.

Operations on Congruence Classes

Addition/Subtraction of Congruence Classes

Given two congruence classes $[a],[b]\in {\mathbb{Z}}_n$, we can define the addition of congruence classes as:

$$[a]\pm [b]=[a\pm b].$$

This definition needs to be justified. Recall in previous section, we shown $[a]=[a+kn]$ and $[b]=[b+mn]$ for any integers $k,m$, we must show that the sum $[a\pm b]$ is independent of the choice of representatives $a$ and $b$. This is indeed correct and we state it as a proposition:

Proposition

For any $a,a^{\prime },b,b^{\prime }\in \mathbb{Z}$, if $[a]=[a^{\prime }]$ and $[b]=[b^{\prime }]$, then $[a\pm b]=[a^{\prime }\pm b^{\prime }]$.

Proof of Proposition

By this proposition, we know $[a]=[a^{\prime }]$ iff $a\equiv a^{\prime }(\mathrm{mod}n)$, and $[b]=[b^{\prime }]$ iff $b\equiv b^{\prime }(\mathrm{mod}n)$. The proposition is equivalent to show that $a\pm b\equiv a^{\prime }\pm b^{\prime }(\mathrm{mod}n)$, and this follows directly from compatibility of congruence relation with addition and subtraction. $■$

Multiplication of Congruence Classes

Given two congruence classes $[a],[b]\in {\mathbb{Z}}_n$, we can define the multiplication of congruence classes as:

$$[a]\cdot [b]=[a\cdot b].$$

This definition also needs to be justified. We can show this operation is well-defined and consistent with the multiplication of integers. We state this as a proposition:

Proposition

For any $a,a^{\prime },b,b^{\prime }\in \mathbb{Z}$, if $[a]=[a^{\prime }]$ and $[b]=[b^{\prime }]$, then $[a\cdot b]=[a^{\prime }\cdot b^{\prime }]$.

Proof of Proposition

By this proposition, we know $[a]=[a^{\prime }]$ iff $a\equiv a^{\prime }(\mathrm{mod}n)$, and $[b]=[b^{\prime }]$ iff $b\equiv b^{\prime }(\mathrm{mod}n)$. The proposition is equivalent to show that $a\cdot b\equiv a^{\prime }\cdot b^{\prime }(\mathrm{mod}n)$, and this follows directly from compatibility of congruence relation with multiplication. $■$

Commutative Diagram

Clearly we are defining the operations on ${\mathbb{Z}}_n$ by descending the operations on $\mathbb{Z}$, and we shown these operations are well-defined and consistent with the operations on integers. We can also view this type of compatibility as a commutative diagram:

$$\begin{array}{ccc}\mathbb{Z}\times \mathbb{Z}& \stackrel{\pm ,\times }{\to }& \mathbb{Z}\\ \downarrow & & \downarrow \\ {\mathbb{Z}}_n\times {\mathbb{Z}}_n& \stackrel{\pm ,\times }{\to }& {\mathbb{Z}}_n\end{array}$$

Where the vertical arrows are the quotient map, and the horizontal arrows are the arithmetic operations. The commutative diagram says that the addition operation on ${\mathbb{Z}}_n$ is consistent with the addition operation on $\mathbb{Z}$ by saying going down and then right is the same as going right and then down.