Definition:Congruence (Number Theory)/Modulo Operation
Jump to navigation
Jump to search
Definition
Let $z \in \R$.
Let $\bmod$ be defined as the modulo operation:
- $x \bmod y := \begin {cases} x - y \floor {\dfrac x y} & : y \ne 0 \\ x & : y = 0 \end {cases}$
Then congruence modulo $z$ is the relation on $\R$ defined as:
- $\forall x, y \in \R: x \equiv y \pmod z \iff x \bmod z = y \bmod z$
The real number $z$ is called the modulus.
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
- 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: $(5)$