Congruence in the set of integers

The goal for the second chapter is to introduce the set ${\mathbb{Z}}_n$, which is a finite set with $n$ elements. It still possesses operations like addition and multiplication, and will be our first example of a ring that is not infinite.

There will a map:

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

where $[a]$ is the congruence class of $a$ modulo $n$. It seems like we are doing nothing but adding a bracket et around $a$, this feeling comes from that we have not defined what a congruence class is.

In this note, we will define the congruence relation on the domain $\mathbb{Z}$ and prove that it is an equivalence relation. We will define the congruence class $[a]$ rigorously in the next note based on the congruence relation.

Congruence Relation

The congruence relation is defined for elements in $\mathbb{Z}$, and we need to fix an integer $n>0$ acting as the modulus.

Definition:

Let $a,b\in \mathbb{Z}$, we say $a$ is congruent to $b$ modulo $n$, denoted as $a\equiv b(\mathrm{mod}n)$, if $n\mid (a-b)$.

We can also read $a\equiv b(\mathrm{mod}n)$ as ”$a$ equals $b$ modulo $n$”. We can also use

$$a{\equiv }_{n}b$$

to denote the same congruence relation.

Warning

We must fix the modulus $n>0$ when we talk about congruence relation. When we write $a\equiv b(\mathrm{mod}n)$ or $a{\equiv }_{n}b$, we must always remember the modulus $n$.

Congruence Relation is an Equivalence Relation

As one may notice, we used the symbol $\equiv$ to denote the congruence relation, the symbol looks like the equality symbol $=$. In fact, the congruence relation satisfies the three properties that we expect from an equality relation, we state it as a theorem.

Theorem

The congruence relation is an equivalence relation, i.e. it satisfies the following three properties:

1. Reflexivity: $a\equiv a(\mathrm{mod}n)$ for all $a\in \mathbb{Z}$.
2. Symmetry: If $a\equiv b(\mathrm{mod}n)$, then $b\equiv a(\mathrm{mod}n)$.
3. Transitivity: If $a\equiv b(\mathrm{mod}n)$ and $b\equiv c(\mathrm{mod}n)$, then $a\equiv c(\mathrm{mod}n)$.

Proof of Theorem

We will prove the three properties one by one.

Reflexivity

Let $a\in \mathbb{Z}$, then $a-a=0$, and $n\mid 0$ for all $n>0$. Therefore, $a\equiv a(\mathrm{mod}n)$ for all $a\in \mathbb{Z}$.

Symmetry

If $a\equiv b(\mathrm{mod}n)$, then $n\mid (a-b)$. Since $n\mid (a-b)$, we have $n\mid (b-a)$. Therefore, $b\equiv a(\mathrm{mod}n)$.

Transitivity

If $a\equiv b(\mathrm{mod}n)$ and $b\equiv c(\mathrm{mod}n)$, then $n\mid (a-b)$ and $n\mid (b-c)$. Therefore, $n\mid (a-b)+(b-c)$, which implies $n\mid (a-c)$, so $a\equiv c(\mathrm{mod}n)$.

Compatibility with Arithmetic Operations

The congruence relation is not just an equivalence relation, it also behaves well with arithmetic operations. We state the following theorem:

Theorem

Let $a,b,c,d\in \mathbb{Z}$, if $a\equiv b(\mathrm{mod}n)$ and $c\equiv d(\mathrm{mod}n)$, then:

1. $a+c\equiv b+d(\mathrm{mod}n)$.
2. $a-c\equiv b-d(\mathrm{mod}n)$.
3. $ac\equiv bd(\mathrm{mod}n)$.

Proof of Theorem

We will prove the three properties one by one.

Addition

If $a\equiv b(\mathrm{mod}n)$ and $c\equiv d(\mathrm{mod}n)$, then $n\mid (a-b)$ and $n\mid (c-d)$. Therefore, $n\mid (a-b)+(c-d)$, which implies $n\mid (a+c)-(b+d)$. Therefore, $a+c\equiv b+d(\mathrm{mod}n)$.

Subtraction

If $a\equiv b(\mathrm{mod}n)$ and $c\equiv d(\mathrm{mod}n)$, then $n\mid (a-b)$ and $n\mid (c-d)$. Therefore, $n\mid (a-b)-(c-d)$, which implies $n\mid (a-c)-(b-d)$. Therefore, $a-c\equiv b-d(\mathrm{mod}n)$.

Multiplication

If $a\equiv b(\mathrm{mod}n)$ and $c\equiv d(\mathrm{mod}n)$, then $n\mid (a-b)$ and $n\mid (c-d)$. Let $a=b+kn$ and $c=d+ln$ for some integers $k,l$. Then we have:

$$\begin{array}{rl}ac-bd& =(b+kn)(d+ln)-bd\\ & =bd+bln+dkn+kl{n}^2-bd\\ & =bln+dkn+kl{n}^2.\end{array}$$

We see that $n\mid bln+dkn+kl{n}^2$, which implies $ac\equiv bd(\mathrm{mod}n)$. $■$