Definition:Congruence (Number Theory)

This page is about Congruence in the context of Number Theory. For other uses, see Congruence.

Definition

Let $z \in \R$.

Definition by Remainder after Division

We define a relation $\RR_z$ on the set of all $x, y \in \R$:

$\RR_z := \set {\tuple {x, y} \in \R \times \R: \exists k \in \Z: x = y + k z}$

This relation is called congruence modulo $z$, and the real number $z$ is called the modulus.

When $\tuple {x, y} \in \RR_z$, we write:

$x \equiv y \pmod z$

and say:

$x$ is congruent to $y$ modulo $z$.

Definition by Modulo Operation

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$

Definition by Integer Multiple

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$

Definition for Integers

The concept of congruence is usually considered in the integer domain.

Let $m \in \Z_{> 0}$.

Definition by Remainder after Division

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

Definition by Modulo Operation

Let $\bmod$ be defined as the modulo operation:

$x \bmod m := \begin{cases} x - m \left \lfloor {\dfrac x m}\right \rfloor & : m \ne 0 \\ x & : m = 0 \end{cases}$

Then congruence modulo $m$ is the relation on $\Z$ defined as:

$\forall x, y \in \Z: x \equiv y \pmod m \iff x \bmod m = y \bmod m$

Definition by Integer Multiple

We also see that $a$ is congruent to $b$ modulo $m$ if their difference is a multiple of $m$:

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$

Modulus of Congruence

The number $m$ in this congruence is known as the modulus of the congruence.

Definition for Zero

$x \equiv y \pmod 0 \iff x \bmod 0 = y \bmod 0 \iff x = y$

and:

$x \equiv y \pmod 0 \iff \exists k \in \Z: x - y = 0 \times k = 0 \iff x = y$

Residue

Let $a, b \in \Z$.

Let $a \equiv b \pmod m$.

Then $b$ is a residue of $a$ modulo $m$.

Residue is another word meaning remainder, and is any integer congruent to $a$ modulo $m$.

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.

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

• Results about congruences 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.