# Definition:Congruence (Number Theory)/Integers

From ProofWiki

## Contents

## Definition

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

Then we define **congruence modulo $m$** as the relation $\equiv \pmod m$ on the set of all $a, b \in \Z$:

- $a \equiv b \pmod m := \left\{{\left({a, b}\right) \in \Z \times \Z: \exists k \in \Z: a = b + km}\right\}$

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

Then **$x$ is congruent to $y$ modulo $m$** iff their difference is an integral multiple of $m$:

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

## Also see

## Sources

- Martin Davis:
*Computability and Unsolvability*(1958)... (previous)... (next): Appendix $1$: Some Results from the Elementary Theory of Numbers: Definition $4$ - John D. Dixon:
*Problems in Group Theory*(1967)... (previous)... (next): Introduction: Notation - Allan Clark:
*Elements of Abstract Algebra*(1971)... (previous)... (next): $\S 18$ - John F. Humphreys:
*A Course in Group Theory*(1996)... (previous)... (next): $\S 2$: Example $2.23$