Definition:Congruence (Number Theory)/Integer Multiple
Definition
Let $z \in \R$.
Let $x, y \in \R$.
Then $x$ is congruent to $y$ modulo $z$ if and only if their difference is an integer multiple of $z$:
- $x \equiv y \pmod z \iff \exists k \in \Z: x - y = k z$
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}$
Examples
Congruence Modulo $1$
Let $x \equiv y \pmod 1$ be defined as congruence on the real numbers modulo $1$:
- $\forall x, y \in \R: x \equiv y \pmod 1 \iff \exists k \in \Z: x - y = k$
That is, if their difference $x - y$ is an integer.
The equivalence classes of this equivalence relation are of the form:
- $\eqclass x 1 = \set {\dotsc, x - 2, x - 1, x, x + 1, x + 2, \dotsc}$
Each equivalence class has exactly one representative in the half-open real interval:
- $\hointr 0 1 = \set {x \in \R: 0 \le x < 1}$
Congruence Modulo $2 \pi$ as Angular Measurement
Let $\RR$ denote the relation on the real numbers $\R$ defined as:
- $\forall x, y \in \R: \tuple {x, y} \in \RR \iff \text {$x$ and $y$}$ measure the same angle in radians
Then $\RR$ is the congruence relation modulo $2 \pi$.
The equivalence classes of this equivalence relation are of the form:
- $\eqclass \theta {2 \pi} = \set {\theta + 2 k \pi: k \in \Z}$
Hence for example:
- $\eqclass 0 {2 \pi} = \set {2 k \pi: k \in \Z}$
and:
- $\eqclass {\dfrac \pi 2} {2 \pi} = \set {\dfrac {\paren {4 k + 1} \pi} 2: k \in \Z}$
Each equivalence class has exactly one representative in the half-open real interval:
- $\hointr 0 {2 \pi} = \set {x \in \R: 0 \le x < 2 \pi}$
and have a one-to-one correspondence with the points on the circumference of a circle.
Also see
- Results about congruence in the context of number theory can be found here.
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
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {4-1}$ Basic Properties of Congruences: Definition $\text {4-1}$
- 1982: P.M. Cohn: Algebra Volume 1 (2nd ed.) ... (previous) ... (next): $\S 2.3$: Congruences
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.4$: Integer Functions and Elementary Number Theory
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): congruence modulo $n$
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): congruence modulo $n$