Definition:Congruence (Number Theory)/Remainder after Division
Jump to navigation
Jump to search
Definition
Let $z \in \R$.
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$.
Similarly, when $\tuple {x, y} \notin \RR_z$, we write:
- $x \not \equiv y \pmod z$
and say:
- $x$ is not congruent (or incongruent) to $y$ modulo $z$.
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 \ \paren {\mathop {\operatorname{modulo} } z}$
Some (usually older) sources render it as:
- $x \equiv y \ \paren {\mathop {\operatorname{mod.} } z}$
Also see
- Results about congruence in the context of number theory 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, published in $1801$.
Linguistic Note
The word modulo comes from the Latin for with modulus, that is, with measure.