Congruence (Number Theory)/Integers/Examples
Examples of Congruence Modulo an Integer
Congruence Modulo 1
Let $x \equiv y \pmod 1$ be defined on the integers as congruence modulo $1$:
- $\forall x, y \in \Z: x \equiv y \pmod 1 \iff \exists k \in \Z: x - y = k$
That is, if their difference $x - y$ is an integer.
The equivalence classes of this equivalence relation is the set of integers:
- $\eqclass x 1 = \Z$
Congruence Modulo 2
Let $x \equiv y \pmod 2$ be defined on the integers as congruence modulo $2$:
- $\forall x, y \in \Z: x \equiv y \pmod 2 \iff \exists k \in \Z: x - y = 2 k$
That is, if their difference $x - y$ is an even integer.
The equivalence classes of this equivalence relation are of the form:
- $\eqclass x 2 = \set {\dotsc, x - 4, x - 2, x, x + 2, x + 4, \dotsc}$
which are:
\(\ds \eqclass 0 2\) | \(=\) | \(\ds \set {\dotsc, -4, -2, 0, 2, 4, \dotsc}\) | that is, the even integers | |||||||||||
\(\ds \eqclass 1 2\) | \(=\) | \(\ds \set {\dotsc, -3, -1, 1, 3, 5, \dotsc}\) | that is, the odd integers |
Each equivalence class has exactly one representative in the set $\set {0, 1}$.
Congruence Modulo 3
Let $x \mathrel \RR y$ be the equivalence relation defined on the integers as congruence modulo $3$:
- $x \mathrel \RR y \iff x \equiv y \pmod 3$
defined as:
- $\forall x, y \in \Z: x \equiv y \pmod 3 \iff \exists k \in \Z: x - y = 3 k$
That is, if their difference $x - y$ is a multiple of $3$.
The equivalence classes of this equivalence relation are of the form:
- $\eqclass x 3 = \set {\dotsc, x - 6, x - 3, x, x + 3, x + 6, \dotsc}$
which are:
\(\ds \eqclass 0 3\) | \(=\) | \(\ds \set {\dotsc, -6, -3, 0, 3, 6, \dotsc}\) | ||||||||||||
\(\ds \eqclass 1 3\) | \(=\) | \(\ds \set {\dotsc, -5, -2, 1, 4, 7, \dotsc}\) | ||||||||||||
\(\ds \eqclass 2 3\) | \(=\) | \(\ds \set {\dotsc, -4, -1, 2, 5, 8, \dotsc}\) |
Thus the partition of $\Z$ induced by $\RR$ is:
- $\Bbb S = \set {\eqclass 0 3, \eqclass 1 3, \eqclass 2 3}$
Each equivalence class has exactly one representative in the set $\set {0, 1, 2}$.