# Definition:Congruence (Number Theory)

## Contents

## Definition

Let $z \in \R$.

### Definition by Remainder after Division

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

- $\mathcal R_z := \left\{{\left({x, y}\right) \in \R \times \R: \exists k \in \Z: x = y + k z}\right\}$

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

When $\left({x, y}\right) \in \mathcal R_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 \left \lfloor {\dfrac x y}\right \rfloor & : 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$

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

## 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

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