Definition:Congruence (Number Theory)/Integers/Remainder after Division

Definition

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

Congruence modulo $m$ is defined as the relation $\equiv \pmod m$ on the set of all $a, b \in \Z$:

$a \equiv b \pmod m := \set {\tuple {a, b} \in \Z \times \Z: \exists k \in \Z: a = b + k m}$

That is, such that $a$ and $b$ have the same remainder when divided by $m$.

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}$

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

1964: Walter Ledermann: Introduction to the Theory of Finite Groups (5th ed.) ... (previous) ... (next): Chapter $\text {I}$: The Group Concept: $\S 6$: Examples of Finite Groups: $\text{(iii)}$
1971: Allan Clark: Elements of Abstract Algebra ... (previous) ... (next): Chapter $1$: Equivalence Relations: $\S 18$
1982: Martin Davis: Computability and Unsolvability (2nd ed.) ... (previous) ... (next): Appendix $1$: Some Results from the Elementary Theory of Numbers: Definition $4$
1996: John F. Humphreys: A Course in Group Theory ... (previous) ... (next): Chapter $2$: Maps and relations on sets: Example $2.23$
2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): congruence