Definition:Congruence (Number Theory)/Remainder after Division

From ProofWiki
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


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.