Definition:Congruence (Number Theory)/Integers/Modulo Operation

Definition

Let $m \in \Z_{>0}$.

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

$x \bmod m := \begin {cases} x - m \floor {\dfrac x m} & : 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$

The integer $m$ is called the modulus.

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

• Congruence Modulo $z$ for real $z$

• Equivalence of Definitions of Congruence

• Congruence Modulo $m$ is Equivalence Relation

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.