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

From ProofWiki
Jump to navigation Jump to search

Definition

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$


In terms of divisibility, this can be rendered:

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


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


Linguistic Note

The word modulo comes from the Latin for with modulus, that is, with measure.


Sources