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

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

• 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.

Sources

• 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$
• 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): congruence class
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): congruence class (residue class)
• 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): congruence