Equivalence of Definitions of Congruence

From ProofWiki
Jump to navigation Jump to search

Theorem

The following definitions of the concept of Congruence in the context of Number Theory are equivalent:


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$


Proof

Let $x_1, x_2, z \in \R$.

Let $x_1 \equiv x_2 \pmod z$ as defined by an equivalence relation.


That is, let $\mathcal R_z$ be the relation 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\}$


Let $\left({x_1, x_2}\right) \in \mathcal R_z$.

Then by definition, $\exists k \in \Z: x_1 = x_2 + k z$.


So, by definition of the modulo operation, we have:

\(\displaystyle x_1 \mod z\) \(=\) \(\displaystyle \left({x_2 + kz}\right) - z \left \lfloor {\frac {x_2 + kz} z}\right \rfloor\)
\(\displaystyle \) \(=\) \(\displaystyle \left({x_2 + kz}\right) - z \left \lfloor {\frac {x_2} z + k}\right \rfloor\)
\(\displaystyle \) \(=\) \(\displaystyle \left({x_2 + kz}\right) - z \left \lfloor {\frac {x_2} z}\right \rfloor + k z\)
\(\displaystyle \) \(=\) \(\displaystyle x_2 - z \left \lfloor {\frac {x_2} z}\right \rfloor\)
\(\displaystyle \) \(=\) \(\displaystyle x_2 \mod z\)

So:

$x_1 \equiv x_2 \pmod z$

in the sense of definition by modulo operation.

$\Box$


Now let $x_1 \equiv x_2 \pmod z$ in the sense of definition by modulo operation.

That is, :$x_1 \equiv x_2 (\bmod\, z) \iff x_1 \mod z = x_2 \mod z$.


Let $z = 0$.

Then by definition, $x_1 \mod 0 = x_1$ and $x_2 \mod 0 = x_2$.

So as $x_1 \mod 0 = x_2 \mod 0$ we have that $x_1 = x_2$.

So $x_1 - x_2 = 0 = 0.z$ and so $x_1 \equiv x_2 \pmod z$ in the sense of definition by integer multiple.


Now suppose $z \ne 0$.

Then from definition of the modulo operation:

$x_1 \mod z = x_1 - z \left \lfloor {\dfrac {x_1} z}\right \rfloor$
$x_2 \mod z = x_2 - z \left \lfloor {\dfrac {x_2} z}\right \rfloor$

Thus:

$x_1 - z \left \lfloor {\dfrac {x_1} z}\right \rfloor = x_2 - z \left \lfloor {\dfrac {x_2} z}\right \rfloor$

and so:

$x_1 - x_2 = z \left({\left \lfloor {\dfrac {x_1} z}\right \rfloor - \left \lfloor {\dfrac {x_2} z}\right \rfloor}\right)$

From the definition of the floor function, we see that both $\left \lfloor {\dfrac {x_1} z}\right \rfloor$ and $\left \lfloor {\dfrac {x_2} z}\right \rfloor$ are integers.

Therefore, so is $\left \lfloor {\dfrac {x_1} z}\right \rfloor - \left \lfloor {\dfrac {x_2} z}\right \rfloor$ an integer.

So $\exists k \in \Z: x_1 - x_2 = k z$.


Thus $x_1 - x_2 = k z$ and:

$x_1 \equiv x_2 \pmod z$

in the sense of definition by integer multiple.

$\Box$


Now let $x_1 \equiv x_2 \pmod z$ in the sense of definition by integer multiple.

That is, $\exists k \in \Z: x_1 - x_2 = k z$.


Then $x_1 = x_2 + k z$ and so $\left({x_1, x_2}\right) \in \mathcal R_z$ where:

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

and so

$x_1 \equiv x_2 \pmod z$

in the sense of definition by equivalence relation.

$\Box$


So all three definitions are equivalent: $(1) \implies (2) \implies (3) \implies (1)$.

$\blacksquare$


Also see