Category:Definitions/Congruence (Number Theory)

This category contains definitions related to congruence in the context of number theory.
Related results can be found in Category:Congruence (Number Theory).

Let $z \in \R$.

Definition by Remainder after Division

We define a relation $\RR_z$ on the set of all $x, y \in \R$:

$\RR_z := \set {\tuple {x, y} \in \R \times \R: \exists k \in \Z: x = y + k z}$

This relation is called congruence modulo $z$, and the real number $z$ is called the modulus.

When $\tuple {x, y} \in \RR_z$, we write:

$x \equiv y \pmod z$

and say:

$x$ is congruent to $y$ modulo $z$.

Definition by Modulo Operation

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

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

x - y \floor {\dfrac x y} & : y \ne 0 \\ x & : y = 0 \end{cases}$

Then congruence modulo $z$ is the relation on $\R$ defined as:

$\forall x, y \in \R: x \equiv y \pmod z \iff x \bmod z = y \bmod z$

Definition by Integer Multiple

Let $x, y \in \R$.

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

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