Definition:Congruence (Number Theory)
Contents
Definition
Let $z \in \R$.
Definition by Remainder after Division
We define a relation $\mathcal R_z$ on the set of all $x, y \in \R$:
- $\mathcal R_z := \left\{{\left({x, y}\right) \in \R \times \R: \exists k \in \Z: x = y + k z}\right\}$
This relation is called congruence modulo $z$, and the real number $z$ is called the modulus.
When $\left({x, y}\right) \in \mathcal R_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 \left \lfloor {\dfrac x y}\right \rfloor & : 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$
Definition for Integers
The concept of congruence is usually considered in the integer domain.
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$
Definition for Zero
- $x \equiv y \pmod 0 \iff x \bmod 0 = y \bmod 0 \iff x = y$
and:
- $x \equiv y \pmod 0 \iff \exists k \in \Z: x - y = 0 \times k = 0 \iff x = y$
Residue
Let $a \in \R$.
A residue of $a$ modulo $z$ is another word meaning remainder, and is any number congruent to $a$ modulo $z$.
Examples
Congruence Modulo 1
Let $x \equiv y \pmod 1$ be defined as congruence on the real numbers modulo $1$:
- $\forall x, y \in \R: x \equiv y \pmod 1 \iff \exists k \in \Z: x - y = k$
That is, if their difference $x - y$ is an integer.
The equivalence classes of this equivalence relation are of the form:
- $\eqclass x 1 = \set {\dotsc, x - 2, x - 1, x, x + 1, x + 2, \dotsc}$
Each equivalence class has exactly one representative in the half-open real interval:
- $\hointr 0 1 = \set {x \in \R: 0 \le x < 1}$
Notation
The relation $x$ is congruent to $y$ modulo $z$, usually denoted:
- $x \equiv y \pmod z$
is also frequently seen denoted as:
- $x \equiv y \ \left({\mathop {\operatorname{modulo} } z}\right)$
Some (usually older) sources render it as:
- $x \equiv y \ \left({\mathop {\operatorname{mod.} } z}\right)$
Also see
- Results about congruences can be found here.
Historical Note
The concept of congruence modulo an integer was first explored by Carl Friedrich Gauss.
He originated the notation $a \equiv b \pmod m$ in his work Disquisitiones Arithmeticae.
Linguistic Note
The word modulo comes from the Latin for with modulus, that is, with measure.