Definition:Congruence (Number Theory)

From ProofWiki
Jump to: navigation, search

Contents

General Definition

Let $z \in \R$.


Definition by Equivalence Relation

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.


If $\left({x, y}\right) \in \mathcal R_z$, we write:

$x \equiv y \pmod z$

and say:

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


Similarly, if $\left({x, y}\right) \notin \mathcal R_z$, we write:

$x \not \equiv y \pmod z$

and say:

$x$ is not congruent (or incongruent) to $y$ modulo $z$.


We have that congruence modulo $z$ is an equivalence relation.


Definition by Modulo Operation

Let $z \in \R$ be defined as the modulo operation.

Then:

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


Definition by Integral Multiple

Equivalently, $x$ is congruent to $y$ modulo $z$ iff their difference is an integral multiple of $z$:

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


Definition for Zero

Note that when $z = 0$ the definition is still meaningful:

$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 \cdot k = 0 \iff x = y$


Definition for Integers

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

Let $m \in \Z, m > 0$.

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

$\mathcal R_m = \left\{{\left({a, b}\right) \in \Z \times \Z: \exists k \in \Z: a = b + km}\right\}$


The other definitions also apply under the same restriction.


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

$a \equiv b \pmod m \iff m \backslash \left({a - b}\right)$


This gives us an alternative method of defining congruence modulo an integer.


Equivalence of Definitions

The definitions as given here are equivalent.


Residue

A residue of $a$ modulo $z$ is another word meaning remainder, and means any number congruent to $a$ modulo $z$.


Historical Note

The concept of congruence modulo an integer was first explored by Carl Friedrich Gauss.


Linguistic Note

The word modulo comes from the Latin for with modulus, that is, with measure.


Sources

Retrieved from "http://www.proofwiki.org/w/index.php?title=Definition:Congruence_(Number_Theory)&oldid=91693"
Personal tools
Namespaces
Variants
Actions
Navigation
ProofWiki.org
ToDo
Toolbox
Google AdSense