The Set of Congruence Classes

In the previous note, we defined the congruence relation on the set of integers $\mathbb{Z}$, and we proved that it is an equivalence relation. In this note, we will define ${\mathbb{Z}}_n$, the set of congruence classes modulo $n$.

Understand the Congruence Classes as formal symbols

We will define a map from $\mathbb{Z}$ to ${\mathbb{Z}}_n$ as follows:

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

where $[a{]}_n$ is the congruence class of $a$ modulo $n$, we will drop the subscript $n$ and write $[a]$ when the modulus is clear from the context.

We would like to give a special name for elements in ${\mathbb{Z}}_n$:

Notation

When we say congruence class modulo n, we mean an element in ${\mathbb{Z}}_n$. When we refer to the elements in ${\mathbb{Z}}_n$, we will call them congruence classes. A congruence class is denoted as $[a]$ for some integer $a$.

As promised, we should have ${\mathbb{Z}}_n$ to be a set with $n$ elements, but from the map above, it seems like we are having infinitely many elements in ${\mathbb{Z}}_n$. Well, even for $a\ne b$, we may have $[a]=[b]$! Namely, you can start with two distinct integers $a$ and $b$, but end up with the same congruence class $[a]=[b]$.

The key point is that we are not considering the elements in ${\mathbb{Z}}_n$ as individual integers, but as equivalence classes, where we are identifying integers according to congruence relation.:w

Let’s begin by treating $[a]\in {\mathbb{Z}}_n$ as formal symbols, and we impose the following identification:

Notation

Two elements $[a],[b]\in {\mathbb{Z}}_n$ are equal if and only if $a\equiv b(\mathrm{mod}n)$.

Now if we just treat $[a]\in {\mathbb{Z}}_n$ as formal symbols, we can observe the following cyclic property:

1. $[0],[1],[2],\dots ,[n-1]$ are all distinct as congruence classes.
2. $[0]=[n]=[2n]=\cdots =[kn]$ for any integer $k$.
3. $[a]=[a+kn]$ for any integer $k$.

So far, we have not defined the congruence classes in ${\mathbb{Z}}_n$ rigorously, we just introduced how to represent them as formal symbols, and how to identify them based on the congruence relation.

Understand the Congruence Classes as Equivalence Classes

One may still feel uncomfortable with the formal symbols $[a]$ and the identification we imposed. We will now propose a better, more concrete way to understand the congruence classes in ${\mathbb{Z}}_n$.

Definition

Let $n>0$ be an integer. The congruence class $[a]\in {\mathbb{Z}}_n$ is a subset of $\mathbb{Z}$ defined as:

$$[a]=\{a+kn\mid k\in \mathbb{Z}\}.$$

Based on this definition, we can show this definition is consistent with the formal symbols:

Proposition

Based on the above definition of congruence classes. Let $a,b\in \mathbb{Z}$, then $[a]=[b]$ if and only if $a\equiv b(\mathrm{mod}n)$.

Proof of Proposition

We will show two directions:

1. If $a\equiv b(\mathrm{mod}n)$, then $[a]=[b]$.
2. If $[a]=[b]$, then $a\equiv b(\mathrm{mod}n)$.

The first direction is easy, if $a\equiv b(\mathrm{mod}n)$, then $a=b+kn$ for some integer $k$. Then we have:

$$\begin{array}{rl}[a]& =\{a+mn\mid m\in \mathbb{Z}\}\\ & =\{b+kn+mn\mid m\in \mathbb{Z}\}\\ & =\{b+(k+m)n\mid m\in \mathbb{Z}\}\\ & =[b].\end{array}$$

For the second direction, if $[a]=[b]$, then we know the following two sets are equal:

$$\begin{array}{rl}[a]& =\{a+kn\mid k\in \mathbb{Z}\},\\ [b]& =\{b+mn\mid m\in \mathbb{Z}\}.\end{array}$$

In particular, $a\in [a]$ and $a\in [b]$, this implies $a=b+kn$ for some integer $k$, which means $a\equiv b(\mathrm{mod}n)$. $■$

Understand the Quotient Map

Now, we have defined the congruence classes in ${\mathbb{Z}}_n$ as subsets of $\mathbb{Z}$, and we have shown that this definition is consistent with the formal symbols we introduced earlier. We can now define the quotient map from $\mathbb{Z}$ to ${\mathbb{Z}}_n$, and give some intuitive justification for the notation of congruence classes and the ambiguity in its representation.

Definition

The quotient map from $\mathbb{Z}$ to ${\mathbb{Z}}_n$ is defined as:

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

Intuitive Remark

The map is surjective, we can image this map is put all integers into $n$ boxes, and all integers in the same box are identified as the same congruence class. Now the problem is how should we label the boxes?

The notation $[a]$ is a self-reference to the box that contains $a$. The map is trying to say “put $a$ into the box that contains $a$, which we will call $[a]$”. The ambiguity in the representation comes from the fact that there will be multiple (infinite) integers in the same box, and we can choose any representative of the box to label it.

One may dislike the ambiguity in the representation of congruence classes. Here is a way of avoiding it using division algorithm:

Proposition

We can express the quotient map as:

$$\begin{array}{rl}\mathbb{Z}& \to {\mathbb{Z}}_n\\ a& \mapsto [a]=[r]\text{ where }r\text{ is the remainder of the division of }a\text{ by }n.\end{array}$$

And there are $n$ distinct congruence classes $[0],[1],\dots ,[n-1]$ in ${\mathbb{Z}}_n$.

The proof is just applying the division algorithm to $a$ and $n$. We will leave it as an exercise.