Congruences

Overview

For each positive integer $n$, the set ${\mathbb{Z}}^{+}$ can be partitioned into $n$ cells according to whether the remainder is $0,1,2,\dots ,n-1$. These cells are called the residue classes modulo $n$ in ${\mathbb{Z}}^{+}$. $n$ is called the modulus.

The equivalence relation on ${\mathbb{Z}}^{+}$ corresponding to the residue classes modulo $n$ in ${\mathbb{Z}}^{+}$ is called congruence modulo $n$. We usually write $a\equiv b(\mathrm{mod}n)$ to state $a$ is congruent to $b$ modulo $n$.

$a\equiv b(\mathrm{mod}n)$ if and only if $n\mid (a-b)$.

Chinese Remainder Theorem

Let $n_1,n_2,\dots ,n_k\in {\mathbb{Z}}^{+}$ be pairwise coprime and $a_1,a_2,\dots ,a_k\in {\mathbb{Z}}^{+}$. Then there exists a unique solution (modulo $N=n_1{n}_2\cdots n_k$) to the following system of congruences:

Equivalently, we note there is a rng isomorphism $\varphi :{\mathbb{Z}}_{n_1{n}_2\cdots n_k}\to {\mathbb{Z}}_{n_1}\times {\mathbb{Z}}_{n_2}\times \cdots \times {\mathbb{Z}}_{n_k}$ given by