Definition:Set of Residue Classes

From ProofWiki
Jump to navigation Jump to search

Definition

Let $m \in \Z$.

Let $\RR_m$ be the congruence relation modulo $m$ on the set of all $a, b \in \Z$:

$\RR_m = \set {\tuple {a, b} \in \Z \times \Z: \exists k \in \Z: a = b + k m}$

Let $\eqclass a m$ be the residue class of $a$ (modulo $m$).


The quotient set of congruence modulo $m$ denoted $\Z_m$ is:

$\Z_m = \dfrac \Z {\RR_m}$


Least Positive Residues

Let $\eqclass a m$ be the residue class of $a$ (modulo $m$).

Let $r$ be the smallest non-negative integer in $\eqclass a m$.


Then from Integer is Congruent to Integer less than Modulus:

$0 \le r < m$

and:

$a \equiv r \pmod m$


Then $r$ is called the least positive residue of $a \pmod m$.


Least Absolute Residues

Let $\eqclass a m$ be the residue class of $a$ (modulo $m$).

Except when $r = \dfrac m 2$, we can choose $r$ to be the integer in $\eqclass a m$ which has the smallest absolute value.

In that exceptional case we have:

$-\dfrac m 2 + m = \dfrac m 2$

and so:

$-\dfrac m 2 \equiv \dfrac m 2 \pmod m$


Thus $r$ is defined as the least absolute residue of $a$ (modulo $m$) if and only if:

$-\dfrac m 2 < r \le \dfrac m 2$


Real Modulus

The quotient set of congruence modulo $z$ denoted $\R_z$ is:

$\R_z = \dfrac \R {\RR_z}$

Thus $\R_z$ is the set of all residue classes modulo $z$.


It follows from the Fundamental Theorem on Equivalence Relations that the quotient set $\R_z$ of congruence modulo $z$ forms a partition of $\R$.


Also known as

The set of residue classes can also be seen as the complete set of residues or complete residue system.

Some sources prefer the term set of all residue classes but it is $\mathsf{Pr} \infty \mathsf{fWiki}$'s opinion that the all is redundant.


Examples

Set of Residue Classes Modulo $2$

The elements of $\Z_2$, the set of residue classes modulo $2$, are:

\(\ds \eqclass 0 2\) \(=\) \(\ds \set {\dotsc, -6, -4, -2, 0, 2, 4, 6, \dotsc}\)
\(\ds \eqclass 1 2\) \(=\) \(\ds \set {\dotsc, -5, -3, -1, 1, 3, 5, \dotsc}\)


Set of Residue Classes Modulo $3$

The elements of $\Z_3$, the set of residue classes modulo $3$, 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, 6, \dotsc}\)


Set of Residue Classes Modulo $4$

The elements of $\Z_4$, the set of residue classes modulo $4$, are:

\(\ds \eqclass 0 4\) \(=\) \(\ds \set {\dotsc, -8, -4, 0, 4, 8, 12, 16, \dotsc}\)
\(\ds \eqclass 1 4\) \(=\) \(\ds \set {\dotsc, -7, -3, 1, 5, 9, 13, 17, \dotsc}\)
\(\ds \eqclass 2 4\) \(=\) \(\ds \set {\dotsc, -6, -2, 2, 6, 10, 14, 18, \dotsc}\)
\(\ds \eqclass 3 4\) \(=\) \(\ds \set {\dotsc, -5, -1, 3, 7, 11, 15, 19, \dotsc}\)


Set of Residue Classes Modulo $5$

The elements of $\Z_5$, the set of residue classes modulo $5$, are:

\(\ds \eqclass 0 5\) \(=\) \(\ds \set {\dotsc, -10, -5, 0, 5, 10, 15, 20, \dotsc}\)
\(\ds \eqclass 1 5\) \(=\) \(\ds \set {\dotsc, -9, -4, 1, 6, 11, 16, 21, \dotsc}\)
\(\ds \eqclass 2 5\) \(=\) \(\ds \set {\dotsc, -8, -3, 2, 7, 12, 17, 22, \dotsc}\)
\(\ds \eqclass 3 5\) \(=\) \(\ds \set {\dotsc, -7, -2, 3, 8, 13, 18, 23, \dotsc}\)
\(\ds \eqclass 4 5\) \(=\) \(\ds \set {\dotsc, -6, -2, 1, 9, 14, 19, 24, \dotsc}\)


Also see

  • Results about residue classes can be found here.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Set_of_Residue_Classes&oldid=613499"