Congruence Relations

Definition

Congruence

Let $a,b\in \mathbb{Z}$ and $n\in {\mathbb{Z}}^{+}$ $a$ is congruent to $b$ modulo $n$ iff $n|(a-b)$ ($a-b$ is divisible by $n$) can be written as $a\equiv b\mathrm{mod}n$

Congruence Relation

Congruence modulo $n$ (mod-$n$) relation $R$: $\forall x,y\in \mathbb{Z}(xRy\iff n|(x-y))$
The quotient $\mathbb{Z}/{\sim }_n$ where ${\sim }_n$ is the congruence-mod-n relation on $\mathbb{Z}$ is denoted ${\mathbb{Z}}_n$

Properties

Congruence modulo $n$ relation is an Equivalence Relations, i.e. it splits the set of integers into partitions.