Category:Examples of Congruence Modulo Integer

From ProofWiki
Jump to navigation Jump to search

This category contains examples of Congruence Modulo Integer.

Let $m \in \Z_{> 0}$.

Definition by Remainder after Division

Congruence modulo $m$ is defined as the relation $\equiv \pmod m$ on the set of all $a, b \in \Z$:

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

That is, such that $a$ and $b$ have the same remainder when divided by $m$.

Definition by Modulo Operation

Let $\bmod$ be defined as the modulo operation:

$x \bmod m := \begin{cases}

x - m \left \lfloor {\dfrac x m}\right \rfloor & : m \ne 0 \\ x & : m = 0 \end{cases}$

Then congruence modulo $m$ is the relation on $\Z$ defined as:

$\forall x, y \in \Z: x \equiv y \pmod m \iff x \bmod m = y \bmod m$

Definition by Integer Multiple

We also see that $a$ is congruent to $b$ modulo $m$ if their difference is a multiple of $m$:

Let $x, y \in \Z$.

$x$ is congruent to $y$ modulo $m$ if and only if their difference is an integer multiple of $m$:

$x \equiv y \pmod m \iff \exists k \in \Z: x - y = k m$