nyuuzyou/wikis huggingface dataset:
Congruence Relation/Examples/Equal Sine of pi x over 6 on Integers for Multiplication

== Example of Congruence Relation ==
Let $\Z$ denote the set of integers.
Let $\RR$ denote the relation on $\Z$ defined as:
:$\forall x, y \in \Z: x \mathrel \RR y \iff \sin \dfrac {\pi x} 6 = \sin \dfrac {\pi y} 6$
Then $\RR$ is not a congruence relation for multiplication on $\Z$.
== Proof ==
;Proof by Counterexample
Note that by Equivalence Relation Examples: Equal $\sin \dfrac {\pi x} 6$ on Integers, $\RR$ is an equivalence relation.
However:
But:
:$\sin \dfrac {\paren {1 \times 4} \pi} 6 = \dfrac {\sqrt 3} 2$
while:
:$\sin \dfrac {\paren {5 \times 2} \pi} 6 = -\dfrac {\sqrt 3} 2$
So while we have:
:$\paren {x_1 \mathrel \RR x_2} \land \paren {y_1 \mathrel \RR y_2}$
where $x_1 = 1$, $x_2 = 5$, $y_1 = 4$, $y_2 = 2$
we have:
:$\paren {x_1 \times y_1} \not \mathrel \RR \paren {x_2 \times y_2}$
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 11$: Quotient Structures: Exercise $11.1 \ \text{(b)}$
Category:Examples of Congruence Relations
Congruence Relation and Ideal are Equivalent

== Theorem ==
Let $\struct {R, +, \circ}$ be a ring.
Let $\EE$ be an equivalence relation on $R$ compatible with both $\circ$ and $+$, that is, a congruence relation on $R$.
Let $J = \eqclass {0_R} \EE$ be the equivalence class of $0_R$ under $\EE$.
Then:
: $(1a): \quad J = \eqclass {0_R} \EE$ is an ideal of $R$
: $(2a): \quad$ The equivalence defined by the quotient ring $R / J$ is $\EE$ itself.
Similarly, let $J$ be an ideal of $R$.
Then:
: $(1b): \quad J$ induces a congruence relation $\EE_J$ on $R$
: $(2b): \quad$ The ideal of $R$ defined by $\EE_J$ is $J$ itself.
== Proof ==
=== Part $(1a)$ ===
This is shown on Congruence Relation on Ring induces Ideal.
=== Part $(2a)$ ===
This is shown on Ideal induced by Congruence Relation defines that Congruence.
=== Part $(1b)$ ===
This is shown on Ideal induces Congruence Relation on Ring.
=== Part $(2b)$ ===
Category:Ideal Theory
Category:Congruence Relations
Congruence Relation induces Normal Subgroup

== Theorem ==
Let $\struct {G, \circ}$ be a group whose identity is $e$.
Let $\RR$ be a congruence relation for $\circ$.
Let $H = \eqclass e \RR$, where $\eqclass e \RR$ is the equivalence class of $e$ under $\RR$.
Then:
:$(1): \quad \struct {H, \circ \restriction_H}$ is a normal subgroup of $G$
:$(2): \quad \RR$ is the equivalence relation $\RR_H$ defined by $H$
:$(3): \quad \struct {G / \RR, \circ_\RR}$ is the subgroup $\struct {G / H, \circ_H}$ of the semigroup $\struct {\powerset G, \circ_\PP}$.
== Proof ==
=== Proof of Normal Subgroup ===
=== Proof of Equality of Relations ===
=== Proof that Quotient Structure is Quotient Group ===
== Also see ==
* Congruence Modulo Normal Subgroup is Congruence Relation, the converse of this result
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 11$: Quotient Structures: Theorem $11.5$
Category:Normal Subgroups
Category:Congruence Relations
Congruence Relation on Group induces Normal Subgroup

== Theorem ==
Let $\struct {G, \circ}$ be a group whose identity is $e$.
Let $\RR$ be a congruence relation for $\circ$.
Let $H = \eqclass e \RR$, where $\eqclass e \RR$ is the equivalence class of $e$ under $\RR$.
Then:
:$\struct {H, \circ \restriction_H}$ is a normal subgroup of $G$
where $\circ \restriction_H$ denotes the restriction of $\circ$ to $H$.
== Proof ==
We are given that $\RR$ is a congruence relation for $\circ$.
From Equivalence Relation is Congruence iff Compatible with Operation, we have:
:$\forall u \in G: x \mathrel \RR y \implies \paren {x \circ u} \mathrel \RR \paren {y \circ u}, \paren {u \circ x} \mathrel \RR \paren {u \circ y}$
==== Proof of being a Subgroup ====
We show that $H$ is a subgroup of $G$.
First we note that $H$ is not empty:
:$e \in H \implies H \ne \O$
Then we show $H$ is closed:
Next we show that $x \in H \implies x^{-1} \in H$:
Thus by the Two-Step Subgroup Test, $H$ is a subgroup of $G$.
==== Proof of Normality ====
Next we show that $H$ is normal in $G$.
Thus:
Thus from Subgroup is Normal iff Contains Conjugate Elements, we have that $H$ is normal.
== Also see ==
* Congruence Relation induces Normal Subgroup
* Normal Subgroup induced by Congruence Relation defines that Congruence
* Quotient Structure on Group defined by Congruence equals Quotient Group
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 11$: Quotient Structures: Theorem $11.5$
Category:Normal Subgroups
Category:Congruence Relations
Congruence Relation on Naturals for Addition Distinct from Equality is Dipper Relation

== Theorem ==
Let $\RR$ be a congruence relation for addition on the natural numbers $\N$.
Let $\RR$ be distinct from the equality relation on $\N$.
Then there exist $m \in \N$ and $n \in \N_{>0}$ such that:
:$\RR = \RR_{m, n}$
where $\RR_{m, n}$ denotes the dipper relation.
== Proof ==
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 16$: The Natural Numbers: Exercise $16.6 \ \text {(c)}$
Category:Dipper Relations
Congruence Relation on Naturals without Zero for Addition Distinct from Equality is Restricted Dipper Relation

== Theorem ==
Let $\RR^*$ be a congruence relation for addition on the non-zero natural numbers $\N_{>0}$.
Let $\RR^*$ be distinct from the equality relation on $\N$.
Then there exist $m, n \in \N_{>0}$ such that:
:$\RR^* = \RR^*_{m, n}$
where $\RR^*_{m, n}$ denotes the restricted dipper relation.
== Proof ==
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 16$: The Natural Numbers: Exercise $16.7 \ \text {(c)}$
Category:Restricted Dipper Relations
Congruence Relation on Ring induces Ideal

== Theorem ==
Let $\struct {R, +, \circ}$ be a ring.
Let $\EE$ be a congruence relation on $R$.
Let $J = \eqclass {0_R} \EE$ be the equivalence class of $0_R$ under $\EE$.
Then $J$ is an ideal of $R$.
== Proof ==
Let $J = \eqclass {0_R} \EE$.
By Congruence Relation induces Normal Subgroup, $\struct {J, +}$ is a normal subgroup of $\struct {R, +}$.
Thus the elements of $\struct {R, +} / \struct {J, +}$ are the cosets of $\eqclass {0_R} \EE$ by $+$.
We have that $\EE$ is also compatible with $\circ$.
Thus from Quotient Structure is Well-Defined, and so:
:$\eqclass {x_1} \EE = \eqclass {x_2} \EE \land \eqclass {y_1} \EE = \eqclass {y_2} \EE \implies \eqclass {x_1 \circ y_1} \EE = \eqclass {x_2 \circ y_2} \EE$
Putting $x_1 = 0_R, x_2 = x, y_1 = y_2 = y$, so that $\eqclass {y_1} \EE = \eqclass {y_2} \EE$ by definition:
:$\eqclass 0 \EE = \eqclass x \EE \implies \eqclass {0 \circ y} \EE = \eqclass {x \circ y} \EE$
Hence:
:$\forall y \in R: \eqclass y \EE \circ \eqclass {0_R} \EE = \eqclass {0_R} \EE = \eqclass {0_R} \EE \circ \eqclass y \EE$
That is:
:$\forall x \in J, y \in R: y \circ x \in J, x \circ y \in J$
demonstrating that $J$ is an ideal of $R$.
== Also see ==
* Ideal induced by Congruence Relation defines that Congruence
* Quotient Ring is Ring
== Sources ==
* : Chapter $\text {IV}$: Rings and Fields: $22$. New Rings from Old: Theorems $22.2$
Category:Congruence Relations
Category:Ideal Theory
Category:Quotient Rings
Congruence Relation on Ring induces Ring

== Theorem ==
Let $\struct {R, +, \circ}$ be a ring.
Let $\EE$ be a congruence relation on $R$ for both $+$ and $\circ$.
Let $R / \EE$ be the quotient set of $R$ by $\EE$.
Let $+_\EE$ and $\circ_\EE$ be the operations induced on $R / \EE$ by $+$ and $\circ$ respectively.
Then $\struct {R / \EE, +_\EE, \circ_\EE}$ is a ring.
== Proof ==
Let $q_\EE$ be the quotient mapping from $\struct {R, +, \circ}$ to $\struct {R / \EE, +_\EE, \circ_\EE}$.
From Quotient Mapping on Structure is Epimorphism:
:$q_\EE: \struct {R, +} \to \struct {R / \EE, +_\EE}$ is an epimorphism
:$q_\EE: \struct {R, \circ} \to \struct {R / \EE, \circ _\EE}$ is an epimorphism.
As the morphism property holds for both $+$ and $\circ$, it follows that $q_\EE: \struct {R, +, \circ} \to \struct {R / \EE, +_\EE, \circ_\EE}$ is also an epimorphism.
From Epimorphism Preserves Rings, it follows that $\struct {R / \EE, +_\EE, \circ_\EE}$ is a ring.
== Sources ==
* : Chapter $\text {IV}$: Rings and Fields: $22$. New Rings from Old: Theorem $22.1$
Category:Congruence Relations
Category:Ring Theory
Congruence by Divisor of Modulus

== Theorem ==
Let $z \in \R$ be a real number.
Let $a, b \in \R$ such that $a$ is congruent modulo $z$ to $b$, that is:
:$a \equiv b \pmod z$
Let $m \in \R$ such that $z$ is an integer multiple of $m$:
:$\exists k \in \Z: z = k m$
Then:
: $a \equiv b \pmod m$
=== Integer Modulus ===
When $z$ is an integer, and therefore a composite number such that $z = r s$, this result can be expressed as:
== Proof ==
We are given that $\exists k \in \Z: z = k m$.
Thus:
== Sources ==
* : $\S 2.3$: Congruences: Theorem $1 \ \text{(iv)}$
Category:Modulo Arithmetic
Congruence by Divisor of Modulus/Integer Modulus

== Theorem ==
Let $r, s \in \Z$ be integers.
Let $a, b \in \Z$ such that $a$ is congruent modulo $r s$ to $b$, that is:
:$a \equiv b \pmod {r s}$
Then:
:$a \equiv b \pmod r$
and:
:$a \equiv b \pmod s$
== Proof ==
== Sources ==
* : $\S 2.5$. Congruence of integers: Example $38$
* : $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $17$
Category:Modulo Arithmetic
Congruence by Factors of Modulo

== Theorem ==
Let $a, b \in \Z$.
Let $r$ and $s$ be coprime integers.
Then:
:$a \equiv b \pmod {r s}$ $a \equiv b \pmod r$ and $a \equiv b \pmod s$
where $a \equiv b \pmod r$ denotes that $a$ is congruent modulo $r$ to $b$.
== Proof ==
=== Necessary Condition ===
This is proved in Congruence by Divisor of Modulus.
Note that for this result it is not required that $r \perp s$.
=== Sufficient Condition ===
Now suppose that $a \equiv b \pmod r$ and $a \equiv b \pmod s$.
We have by definition of congruence:
:$a \equiv b \pmod r \implies \exists k \in \Z: a - b = k r$
From $a \equiv b \pmod s$ we also have that:
:$k r \equiv 0 \pmod s$
As $r \perp s$, we have from Common Factor Cancelling in Congruence:
:$k \equiv 0 \pmod s$
So:
:$\exists q \in \Z: a - b = q s r$
Hence by definition of congruence:
:$a \equiv b \pmod {r s}$
== Examples ==
== Warning ==
== Sources ==
* : $\S 1.2.4$: Integer Functions and Elementary Number Theory: Law $\text{D}$
* : $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $18$
Category:Congruence by Factors of Modulo
Category:Modulo Arithmetic
Congruence by Factors of Modulo/Examples/n = 7 mod 12 so n = 3 mod 4

== Example of use of Congruence by Factors of Modulo ==
Let $n \equiv 7 \pmod {12}$.
Then:
:$n \equiv 3 \pmod 4$
== Proof ==
By the Congruence by Factors of Modulo:
:$n \equiv 7 \pmod {12} \iff n \equiv 7 \pmod 3 \text { and } n \equiv 7 \pmod 4$
as $3$ and $4$ are coprime.
Thus given the hypothesis:
== Sources ==
* : Chapter $2$: Some Properties of $\Z$: Exercise $2.7$
Category:Examples of Congruence by Factors of Modulo
Congruence by Factors of Modulo/Warning

== Theorem ==
Let $a, b, r, s \in \Z$.
Let $r$ not be coprime to $s$.
Then it is not necessarily the case that:
:$a \equiv b \pmod {r s}$ $a \equiv b \pmod r$ and $a \equiv b \pmod s$
where $a \equiv b \pmod r$ denotes that $a$ is congruent modulo $r$ to $b$.
== Proof ==
Proof by Counterexample:
Let $a = 30, b = 40, r = 2, s = 10$.
We have that:
== Sources ==
* : $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $23$
Category:Congruence by Factors of Modulo
Congruence by Product of Moduli

== Theorem ==
Let $a, b, m \in \Z$.
Let $a \equiv b \pmod m$ denote that $a$ is congruent to $b$ modulo $m$.
Then $\forall n \in \Z, n \ne 0$:
:$a \equiv b \pmod m \iff a n \equiv b n \pmod {m n}$
=== Real Modulus ===
== Proof ==
Let $n \in \Z: n \ne 0$.
Then:
Hence the result.
Note the invalidity of the third step when $n = 0$.
== Sources ==
* : $\S 1.2.4$: Integer Functions and Elementary Number Theory: Law $\text{C}$
Category:Modulo Arithmetic
Congruence by Product of Moduli/Real Modulus

== Theorem ==
Let $a, b, z \in \R$.
Let $a \equiv b \pmod z$ denote that $a$ is congruent to $b$ modulo $z$.
Then $\forall y \in \R, y \ne 0$:
:$a \equiv b \pmod z \iff y a \equiv y b \pmod {y z}$
== Proof ==
Let $y \in \R: y \ne 0$.
Then:
Hence the result.
Note the invalidity of the third step when $y = 0$.
== Sources ==
* : $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $24$
Category:Modulo Arithmetic
Congruence of Powers

== Theorem ==
Let $a, b \in \R$ and $m \in \Z$.
Let $a$ be congruent to $b$ modulo $m$, that is:
:$a \equiv b \pmod m$
Then:
:$\forall n \in \Z_{\ge 0}: a^n \equiv b^n \pmod m$
== Proof ==
Proof by induction:
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:$a \equiv b \implies a^k \equiv b^k \pmod m$
$\map P 0$ is trivially true, as $a^0 = b^0 = 1$.
$\map P 1$ is true, as this just says:
:$a \equiv b \pmod m$
=== Basis for the Induction ===
$\map P 2$ is the case:
:$a^2 \equiv b^2 \pmod m$
which follows directly from the fact that Modulo Multiplication is Well-Defined.
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $\map P k$ is true, where $k \ge 2$, then it logically follows that $\map P {k + 1}$ is true.
So this is our induction hypothesis:
:$a \equiv b \implies a^k \equiv b^k \pmod m$
Then we need to show:
:$a \equiv b \implies a^{k + 1} \equiv b^{k + 1} \pmod m$
=== Induction Step ===
This is our induction step:
Suppose $a^k \equiv b^k \pmod m$.
Then $a^k a \equiv b^k b \pmod m$ by definition of modulo multiplication.
Thus $a^{k + 1} \equiv b^{k + 1} \pmod m$.
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\forall n \in \Z_+: a \equiv b \implies a^n \equiv b^n \pmod m$
== Sources ==
* : $\S 14.4 \ \text{(ii)}$: Congruence modulo $m$ ($m \in \N$)
Category:Modulo Arithmetic
Congruence of Product

== Theorem ==
Let $a, b, z \in \R$.
Let $a$ be congruent to $b$ modulo $z$, that is:
:$a \equiv b \pmod z$
Then:
:$\forall m \in \Z: m a \equiv m b \pmod z$
== Proof ==
Let $m \in \Z$ and $a \equiv b \pmod z$.
Suppose $m = 0$.
Then the of the assertion degenerates to $0 \equiv 0 \pmod z$ which is trivially true.
Otherwise, from Congruence by Product of Moduli, we have:
:$a \equiv b \iff m a \equiv m b \pmod z$
As $m \in \Z$, it follows that $m z$ is an integer multiple of $z$.
Hence from Congruence by Divisor of Modulus, it follows that:
:$m a \equiv m b \implies m a \equiv m b \pmod z$
== Sources ==
* : $\S 14.4 \ \text{(i)}$: Congruence modulo $m$ ($m \in \N$)
Category:Modulo Arithmetic
Congruence of Quotient

== Theorem ==
Let $a, b \in \Z$ and $n \in \N$.
Let $a$ be congruent to $b$ modulo $n$, that is $a \equiv b \pmod n$.
Let $d \in \Z: d > 0$ such that $d$ is a common divisor of $a, b$ and $n$.
Then:
:$\dfrac a d \equiv \dfrac b d \pmod {n / d}$
== Proof 1 ==
== Proof 2 ==
== Examples ==
== Warning ==
== Sources ==
* 
* 
Category:Congruence of Quotient
Category:Modulo Arithmetic
Congruence of Quotient/Proof 1

== Theorem ==
== Proof ==
By definition of congruence modulo $n$:
:$a = b + k n$
Dividing through by $d$ (which you can do because $d$ divides all three terms), we get:
:$\dfrac a d = \dfrac b d + k \dfrac n d$
from which the result follows directly.
Category:Congruence of Quotient
Congruence of Quotient/Proof 2

== Theorem ==
== Proof ==
From Congruence by Product of Moduli, we have that:
:$\dfrac a d \equiv \dfrac b d \pmod {n / d} \iff d \dfrac a d \equiv d \dfrac b d \pmod {n / d} \iff a \equiv b \pmod n$
Category:Congruence of Quotient
Congruence of Quotient/Warning

== Congruence of Quotient: Warning ==
Note that in general it is not the case that:
For example:
But we may not conclude that:
:$\dfrac 8 {27} \pmod {10} = \dfrac {18} 7 \pmod {10}$
We may not even conclude that:
:$\dfrac 8 2 \pmod {10} = \dfrac {18} 2 \pmod {10}$
because:
But we do have:
== Sources ==
* 
* 
Category:Congruence of Quotient
Congruence of Sum of Digits to Base Less 1

== Theorem ==
Let $x \in \Z$, and $b \in \N, b > 1$.
Let $x$ be written in base $b$:
:$x = \sqbrk {r_m r_{m - 1} \ldots r_2 r_1 r_0}_b$
Then:
:$\ds \map {s_b} x = \sum_{j \mathop = 0}^m r_j \equiv x \pmod {b - 1}$
where $\map {s_b} x$ is the digit sum of $x$ in base $b$ notation.
That is, the digit sum of any integer $x$ in base $b$ notation is congruent to $x$ modulo $b - 1$.
== Proof ==
Let $x \in \Z, x > 0$, and $b \in \N, b > 1$.
Then from the Basis Representation Theorem, $x$ can be expressed uniquely as:
:$\ds x = \sum_{j \mathop = 0}^m r_j b^j, r_0, r_1, \ldots, r_m \in \set {0, 1, \ldots, b - 1}$
Proof by induction:
For all $n \in \N_{>0}$, let $\map P n$ be the proposition $\ds \sum_{j \mathop = 0}^n r_j \equiv x \pmod {b - 1}$.
=== Basis for the Induction ===
$\map P 1$ is trivially true:
:$\forall x: 0 \le x \le b: x \equiv x \pmod {b - 1}$
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $\map P k$ is true, where $k \ge 2$, then it logically follows that $\map P {k + 1}$ is true.
So this is our induction hypothesis:
:$\ds \sum_{j \mathop = 0}^k r_j \equiv \sum_{j \mathop = 0}^k r_j b^j \pmod {b - 1}$
Then we need to show:
:$\ds \sum_{j \mathop = 0}^{k \mathop + 1} r_j \equiv \sum_{j \mathop = 0}^{k \mathop + 1} r_j b^j \pmod {b - 1}$
=== Induction Step ===
This is our induction step:
Let $y$ be expressed as:
:$\ds y = \sum_{j \mathop = 0}^{k \mathop + 1} {r_j b^j}, r_0, r_1, \ldots, r_{k + 1} \in \set {0, 1, \ldots, b}$
Then:
:$\ds y = \sum_{j \mathop = 0}^k r_j b^j + r_{k + 1} b^{k + 1}$
Now from Congruence of Powers:
:$b \equiv 1 \pmod {b - 1} \leadsto b^n \equiv 1^n \pmod {b - 1} \leadsto b^n \equiv 1 \pmod {b - 1}$
So by modulo multiplication:
:$r_{k + 1} b^{k + 1} \equiv r_{k + 1} \pmod {b - 1}$
From the induction hypothesis:
:$\ds \sum_{j \mathop = 0}^{k \mathop + 1} r_j \equiv y \pmod {b - 1}$
Thus by modulo addition:
:$\ds \sum_{j \mathop = 0}^{k \mathop + 1} r_j \equiv \sum_{j \mathop = 0}^k r_j + r_{k + 1} \pmod {b - 1}$
Hence $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction:
:$\ds \sum_{j \mathop = 0}^n r_j \equiv \sum_{j \mathop = 0}^n r_j b^j \pmod {b - 1}$
Category:Number Theory
Congruence of Sum with Constant

== Theorem ==
Let $a, b, z \in \R$.
Let $a$ be congruent to $b$ modulo $z$:
: $a \equiv b \pmod z$
Then:
:$\forall c \in \R: a + c \equiv b + c \pmod z$
== Proof ==
Follows directly from the definition of Modulo Addition:
Category:Modulo Addition
Congruence of Triangles is Equivalence Relation

== Theorem ==
Let $S$ denote the set of all triangles in the plane.
Let $\triangle A \cong \triangle B$ denote the relation that $\triangle A$ is congruent to $\triangle B$.
Then $\cong$ is an equivalence relation on $S$.
== Proof ==
Checking in turn each of the criteria for equivalence:
=== Reflexivity ===
Let $\triangle A$ be a triangle.
By definition, by Triangle Side-Side-Side Congruence, $\triangle A$ is trivially congruent to itself.
Thus $\cong$ is seen to be reflexive.
=== Symmetry ===
Let $\triangle A \cong \triangle B$.
Then:
:all the sides of $\triangle A$ are equal to the sides of $\triangle B$
:all the angles contained by the sides of $\triangle A$ are equal to the angles contained by the sides of $\triangle B$.
It follows directly that:
:all the sides of $\triangle B$ are equal to the sides of $\triangle A$
:all the angles contained by the sides of $\triangle B$ are equal to the angles contained by the sides of $\triangle A$.
That is:
:$\triangle B \cong \triangle A$
Thus $\cong$ is seen to be symmetric.
=== Transitivity ===
Let:
:$\triangle A \cong \triangle B$
:$\triangle B \cong \triangle C$
Then:
:all the sides of $\triangle A$ are equal to the sides of $\triangle B$
:all the angles contained by the sides of $\triangle A$ are equal to the angles contained by the sides of $\triangle B$.
and:
:all the sides of $\triangle B$ are equal to the sides of $\triangle C$
:all the angles contained by the sides of $\triangle B$ are equal to the angles contained by the sides of $\triangle C$.
From Equality is Equivalence Relation, it follows that:
:all the sides of $\triangle A$ are equal to the sides of $\triangle C$
:all the angles contained by the sides of $\triangle A$ are equal to the angles contained by the sides of $\triangle C$.
That is:
:$\triangle A \cong \triangle C$
Thus $\cong$ is seen to be transitive.
$\cong$ has been shown to be reflexive, symmetric and transitive.
Hence by definition it is an equivalence relation.
== Sources ==
* : $3$: Continuity generalized: topological spaces: $3.6$: Homeomorphisms: Examples $3.6.2 \ \text{(e)}$
::in passing
* : Appendix $\text{A}.3$: Equivalence Relations: $(4)$
Category:Examples of Equivalence Relations
Category:Triangles
Congruences on Rational Numbers

== Theorem ==
There are only two congruence relations on the field of rational numbers $\struct {\Q, +, \times}$:
:$(1): \quad$ The diagonal relation $\Delta_\Q$
:$(2): \quad$ The trivial relation $\Q \times \Q$.
== Proof ==
From:
:Diagonal Relation is Universally Congruent and
:Trivial Relation is Universally Congruent
we know that both these relations are congruent with both addition and multiplication on $\Q$.
Now we need to show that these are the only such relations.
Let $\RR$ be a congruence on $\Q$, such that $\RR \ne \Delta_\Q$.
Then:
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 11$: Quotient Structures: Example $11.3$
Category:Congruence Relations
Category:Rational Numbers
Congruent Integers are of same Quadratic Character

== Theorem ==
Let $p$ be an odd prime.
Let $a \in \Z$ be an integer such that $a \not \equiv 0 \pmod p$.
Let $a \equiv b \pmod p$.
Then $a$ and $b$ have the same quadratic character.
== Proof ==
Let $a \equiv b \pmod p$.
Then by Congruence of Powers:
:$a^2 \equiv b^2 \pmod p$
Hence:
:$x^2 \equiv a \pmod p$ has a solution $x^2 \equiv b \pmod p$.
Hence the result.
Category:Quadratic Residues
Congruent Integers in Same Residue Class

== Theorem ==
Let $m \in \Z_{>0}$ be a (strictly) positive integer.
Let $\Z_m$ be the set of residue classes modulo $m$:
:$\Z_m = \set {\eqclass 0 m, \eqclass 1 m, \dotsc, \eqclass {m - 1} m}$
Let $a, b \in \set {0, 1, \ldots, m -1 }$.
Then:
:$\eqclass a m = \eqclass b m \iff a \equiv b \pmod m$
== Proof ==
By definition of the set of residue classes modulo $m$, $\Z_m$ is the quotient set of congruence modulo $m$:
:$\Z_m = \dfrac \Z {\RR_m}$
where $\RR_m$ is the congruence relation modulo $m$ on the set of all $a, b \in \Z$:
:$\RR_m = \set {\tuple {a, b} \in \Z \times \Z: \exists k \in \Z: a = b + k m}$
By the Fundamental Theorem on Equivalence Relations, $\Z_m$ is a partition of $\Z$.
Thus:
:$\eqclass a m = \eqclass b m$
:
:$x \in \eqclass a m \iff x \in \eqclass b m$
:
:$a \equiv b \pmod m$
== Sources ==
* : $\S 18.1$: Congruence classes
Category:Residue Classes
Congruent Integers less than Half Modulus are Equal

== Theorem ==
Let $k \in \Z_{>0}$ be a strictly positive integer.
Let $a, b \in \Z$ such that $\size a < \dfrac k 2$ and $\size b < \dfrac k 2$.
Then:
:$a \equiv b \pmod k \implies a = b$
where $\equiv$ denotes congruence modulo $k$.
== Proof ==
We have that:
:$-\dfrac k 2 < a < \dfrac k 2$
and:
:$-\dfrac k 2 < -b < \dfrac k 2$
Thus:
:$-k < a - b < k$
Let $a \equiv b \pmod k$
Then:
:$a - b = n k$
for some $n \in \Z$.
But as $-k < n k < k$ it must be the case that $n = 0$.
Thus $a - b = 0$ and the result follows.
== Sources ==
* : $\text {4-1}$ Basic Properties of Congruences: Exercise $5$
Category:Modulo Arithmetic
Congruent Numbers are not necessarily Equal

== Theorem ==
Let $x, y, z \in \R$ be real numbers such that:
:$x \equiv y \pmod z$
where $x \equiv y \pmod z$ denotes congruence modulo $z$.
Then it is not necessarily the case that $x = y$.
== Proof ==
Proof by Counterexample:
We have that:
:$11 - 5 = 6 = 3 \times 2$
and so by definition of congruence modulo $2$:
:$10 \equiv 4 \pmod 2$
But $11 \ne 5$.
== Also see ==
* Equal Numbers are Congruent
== Sources ==
* : $\text {4-1}$ Basic Properties of Congruences: Example $\text {4-3}$
Category:Modulo Arithmetic
Congruent Powers of Root of Unity are Equal

== Theorem ==
Let $n \in \Z_{>0}$ be a strictly positive integer.
Let $F$ be a field.
Let $\alpha$ be an $n$th root of unity.
Let $k, l \in \Z$ such that $k \equiv l \pmod n$.
Then:
:$\alpha^k = \alpha^l$
== Proof ==
By :
:$\exists c \in \Z : k = l + c n$
We have:
Category:Roots of Unity