Category:Examples of Congruence (Number Theory)

From ProofWiki
Jump to navigation Jump to search

This category contains examples of 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$