Congruence (Number Theory)/Integers/Examples/Modulo 3

From ProofWiki
Jump to navigation Jump to search

Example of Congruence Modulo an Integer

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}$.


So, for example, $\eqclass {17} 3 = \set {\dotsc -1, 2, 5, \dotsc, 14, 17, 20, 23, \dotsc}$


Sources