Definition:Congruence (Number Theory)/Integers/Integer Multiple

From ProofWiki
Jump to navigation Jump to search


Let $m \in \Z_{> 0}$ be an integer.

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$

Also denoted as

This is often expressed in terms of divisibility:

$x \equiv y \pmod m \iff m \divides \paren {x - y}$


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.