Definition:Congruence (Number Theory)/Integers

From ProofWiki
Jump to navigation Jump to search

Definition

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 \floor {\dfrac x m} & : 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 for remainder, and is any integer congruent to $a$ modulo $m$.


Examples

Congruence Modulo 1

Let $x \equiv y \pmod 1$ be defined on the integers as congruence modulo $1$:

$\forall x, y \in \Z: 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 is the set of integers:

$\eqclass x 1 = \Z$


Congruence Modulo 2

Let $x \equiv y \pmod 2$ be defined on the integers as congruence modulo $2$:

$\forall x, y \in \Z: x \equiv y \pmod 2 \iff \exists k \in \Z: x - y = 2 k$

That is, if their difference $x - y$ is an even integer.


The equivalence classes of this equivalence relation are of the form:

$\eqclass x 2 = \set {\dotsc, x - 4, x - 2, x, x + 2, x + 4, \dotsc}$

which are:

\(\ds \eqclass 0 2\) \(=\) \(\ds \set {\dotsc, -4, -2, 0, 2, 4, \dotsc}\) that is, the even integers
\(\ds \eqclass 1 2\) \(=\) \(\ds \set {\dotsc, -3, -1, 1, 3, 5, \dotsc}\) that is, the odd integers


Each equivalence class has exactly one representative in the set $\set {0, 1}$.


Congruence Modulo 3

Let $x \mathrel \RR y$ be the equivalence relation defined on the integers as congruence modulo $3$:

$x \mathrel \RR y \iff x \equiv y \pmod 3$

defined as:

$\forall x, y \in \Z: x \equiv y \pmod 3 \iff \exists k \in \Z: x - y = 3 k$

That is, if their difference $x - y$ is a multiple of $3$.


The equivalence classes of this equivalence relation are of the form:

$\eqclass x 3 = \set {\dotsc, x - 6, x - 3, x, x + 3, x + 6, \dotsc}$

which are:

\(\ds \eqclass 0 3\) \(=\) \(\ds \set {\dotsc, -6, -3, 0, 3, 6, \dotsc}\)
\(\ds \eqclass 1 3\) \(=\) \(\ds \set {\dotsc, -5, -2, 1, 4, 7, \dotsc}\)
\(\ds \eqclass 2 3\) \(=\) \(\ds \set {\dotsc, -4, -1, 2, 5, 8, \dotsc}\)

Thus the partition of $\Z$ induced by $\RR$ is:

$\Bbb S = \set {\eqclass 0 3, \eqclass 1 3, \eqclass 2 3}$


Each equivalence class has exactly one representative in the set $\set {0, 1, 2}$.


Further Specific Examples

Congruence Modulo $2$: $8 \equiv 2 \pmod 2$

$8 \equiv 2 \pmod 2$


Congruence Modulo $2$: $8 \not \equiv 3 \pmod 2$

$8 \not \equiv 3 \pmod 2$


Congruence Modulo $2$: $-3 \equiv -5 \pmod 2$

$-3 \equiv -5 \pmod 2$


Congruence Modulo $3$: $12 \equiv 0 \pmod 3$

$12 \equiv 0 \pmod 3$


Congruence Modulo $4$: $2 \equiv -6 \pmod 4$

$2 \equiv -6 \pmod 4$


Congruence Modulo $4$: $3 \equiv 15 \pmod 4$

$3 \equiv 15 \pmod 4$


Congruence Modulo $5$: $3 \equiv 18 \pmod 5$

$3 \equiv 18 \pmod 5$


Congruence Modulo $5$: $13 \equiv 3 \pmod 5$

$13 \equiv 3 \pmod 5$


Congruence Modulo $5$: $17 \equiv 12 \pmod 5$

$17 \equiv 12 \pmod 5$


Congruence Modulo $6$: $-10 \equiv 8 \pmod 6$

$-10 \equiv 8 \pmod 6$


Congruence Modulo $8$: $-2 \equiv 14 \pmod 8$

$-2 \equiv 14 \pmod 8$


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


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

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Congruence_(Number_Theory)/Integers&oldid=700957"