nyuuzyou/wikis huggingface dataset:
Congruence Modulo 3 of Power of 2

== Theorem ==
Let $n \in \Z_{\ge 0}$ be a positive integer.
Then:
:$2^n \equiv \paren {-1}^n \pmod 3$
where $\equiv$ denotes congruence.
That is:
:$\exists q \in \Z: 2^n = 3 q + \paren {-1}^n$
== Proof ==
The proof proceeds by induction.
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:$2^n \equiv \paren {-1}^n \pmod 3$
$\map P 0$ is the case:
Thus $\map P 0$ is seen to hold.
=== Basis for the Induction ===
$\map P 1$ is the case:
Thus $\map P 1$ is seen to hold.
This is the basis for the induction.
=== Induction Hypothesis ===
Now it needs to be shown 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 the induction hypothesis:
:$2^k \equiv \paren {-1}^k \pmod 3$
from which it is to be shown that:
:$2^{k + 1} \equiv \paren {-1}^{k + 1} \pmod 3$
=== Induction Step ===
This is the induction step:
If $k$ is odd, this means:
If $k$ is even, this means:
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\forall n \in \Z_{\ge 0}: 2^n \equiv \paren {-1}^n \pmod 3$
Category:Examples of Congruence Modulo Integer
Category:2
Category:3
Congruence Modulo Equivalence for Integers in P-adic Integers

== Theorem ==
Let $\Z_p$ be the $p$-adic integers for some prime $p$.
For any $a, b \in \Z_p$ and $n \in \N$, let $x \equiv y \pmod{p^n \Z_p}$ denote congruence modulo the principal ideal $p^n\Z_p$.
For any integers $a, b \in \Z$ and $n \in \N$, let $x \equiv y \pmod{p^n}$ denote congruence modulo integer $p^n$.
Let $x, y \in \Z$ be integers.
Let $k \in \N_{>0}$.
:$(1)\quad x \equiv y \pmod{p^k \Z_p}$
:$(2)\quad x \equiv y \pmod{p^k}$
:$(3)\quad p^k \divides \paren{x - y}$
== Proof ==
=== Lemma ===
We have:
Category:P-adic Integers
Category:Congruence Modulo Equivalence for Integers in P-adic Integers
Congruence Modulo Equivalence for Integers in P-adic Integers/Lemma 1

== Theorem ==
Let $\Z_p$ be the $p$-adic integers for some prime $p$.
Let $k \in \N_{>0}$.
Then:
:$\forall a \in \Z: \dfrac a {p^k} \in \Z_p \iff \dfrac a {p^k} \in \Z$
== Proof ==
=== Necessary Condition ===
Let $a \in \Z$.
We have:
=== Sufficient Condition ===
From Integers are Dense in P-adic Integers:
:$\Z \subseteq \Z_p$
The result follows.
Category:Congruence Modulo Equivalence for Integers in P-adic Integers
Congruence Modulo Integer/Examples

== Examples of Congruence Modulo an Integer ==
=== Congruence Modulo $2$: $8 \equiv 2 \pmod 2$ ===
=== Congruence Modulo $2$: $8 \not \equiv 3 \pmod 2$ ===
=== Congruence Modulo $2$: $-3 \equiv -5 \pmod 2$ ===
=== Congruence Modulo $3$: $12 \equiv 0 \pmod 3$ ===
=== Congruence Modulo $4$: $2 \equiv -6 \pmod 4$ ===
=== Congruence Modulo $4$: $3 \equiv 15 \pmod 4$ ===
=== Congruence Modulo $5$: $3 \equiv 18 \pmod 5$ ===
=== Congruence Modulo $5$: $13 \equiv 3 \pmod 5$ ===
=== Congruence Modulo $5$: $17 \equiv 12 \pmod 5$ ===
=== Congruence Modulo $6$: $-10 \equiv 8 \pmod 6$ ===
=== Congruence Modulo $8$: $-2 \equiv 14 \pmod 8$ ===
=== Congruence Modulo $12$: $11 \equiv -1 \pmod {12}$ ===
=== Congruence Modulo $20$: $100 \equiv -40 \pmod {20}$ ===
=== Congruence Modulo $12 \, 345 \, 678$: $12 \, 345 \, 678 \, 987 \, 654 \, 321 \not \equiv 0 \pmod {12 \, 345 \, 678}$ ===
=== Congruence Modulo $12 \, 345 \, 679$: $12 \, 345 \, 678 \, 987 \, 654 \, 321 \equiv 0 \pmod {12 \, 345 \, 679}$ ===
=== Congruence Modulo $4$: $57 \not \equiv 208 \pmod 4$ ===
=== Congruence Modulo $7561$: $531 \not \equiv 1236 \pmod {7561}$ ===
=== Congruence Modulo $3$: $12321 \equiv 111 \pmod 3$ ===
Category:Examples of Congruence Modulo Integer
Congruence Modulo Integer/Examples/-10 equiv 8 mod 6

== Example of Congruence Modulo an Integer ==
:$-10 \equiv 8 \pmod 6$
== Proof ==
By definition of congruence:
:$x \equiv y \pmod n$ $x - y = k n$
for some $k \in \Z$.
We have:
:$-10 - 8 = -18 = \paren {-3} \times 6$
Thus:
:$-10 \equiv 8 \pmod 6$
== Sources ==
* : $\S 2.5$. Congruence of integers: Example $38$
Category:Examples of Congruence Modulo Integer
Congruence Modulo Integer/Examples/-2 equiv 14 mod 8

== Example of Congruence Modulo an Integer ==
:$-2 \equiv 14 \pmod 8$
== Proof ==
By definition of congruence:
:$x \equiv y \pmod n$ $x - y = k n$
for some $k \in \Z$.
We have:
:$\paren {-2} - 14 = -16 = \paren {-2} \times 8$
Thus:
:$-2 \equiv 14 \pmod 8$
== Sources ==
* : Chapter $\text {I}$: The Group Concept: $\S 6$: Examples of Finite Groups: $\text{(iii)}$
Category:Examples of Congruence Modulo Integer
Congruence Modulo Integer/Examples/-3 equiv -5 mod 2

== Example of Congruence Modulo an Integer ==
:$-3 \equiv -5 \pmod 2$
== Proof ==
By definition of congruence:
:$x \equiv y \pmod n$ $x - y = k n$
for some $k \in \Z$.
We have:
:$-3 - \paren {-5} = 2 = 1 \times 2$
Thus:
:$-3 \equiv -5 \pmod 2$
== Sources ==
* : $\S 2.5$. Congruence of integers: Example $38$
Category:Examples of Congruence Modulo Integer
Congruence Modulo Integer/Examples/100 equiv -40 mod 20

== Example of Congruence Modulo an Integer ==
:$100 \equiv -40 \pmod {20}$
== Proof ==
By definition of congruence:
:$x \equiv y \pmod n$ $x - y = k n$
for some $k \in \Z$.
We have:
:$100 - \paren {-40} = 140 = 7 \times 20$
Thus:
:$100 \equiv -40 \pmod {20}$
== Sources ==
* : $\text {4-1}$ Basic Properties of Congruences: Example $\text {4-1}$
Category:Examples of Congruence Modulo Integer
Congruence Modulo Integer/Examples/11 equiv -1 mod 12

== Example of Congruence Modulo an Integer ==
:$11 \equiv -1 \pmod {12}$
== Proof ==
By definition of congruence:
:$x \equiv y \pmod n$ $x - y = k n$
for some $k \in \Z$.
We have:
:$11 - \paren {-1} = 12 = 1 \times 12$
Thus:
:$11 \equiv -1 \pmod {12}$
== Sources ==
* : $\text {4-1}$ Basic Properties of Congruences: Example $\text {4-1}$
Category:Examples of Congruence Modulo Integer
Congruence Modulo Integer/Examples/12,345,678,987,654,321 equiv 0 mod 12,345,679

== Example of Congruence Modulo an Integer ==
:$12 \, 345 \, 678 \, 987 \, 654 \, 321 \equiv 0 \pmod {12 \, 345 \, 679}$
== Proof ==
By definition of congruence:
:$x \equiv y \pmod n$ $x - y = k n$
for some $k \in \Z$.
We have:
:$12 \, 345 \, 678 \, 987 \, 654 \, 321 - 0 = 12 \, 345 \, 678 \, 987 \, 654 \, 321 = 999 \, 999 \, 999 \times 12 \, 345 \, 679$
Thus:
:$12 \, 345 \, 678 \, 987 \, 654 \, 321 \equiv 0 \pmod {12 \, 345 \, 679}$
== Sources ==
* : $\text {4-1}$ Basic Properties of Congruences: Exercise $7 \ \text{(b)}$
Category:Examples of Congruence Modulo Integer
Category:12,345,679
Congruence Modulo Integer/Examples/12,345,678,987,654,321 not equiv 0 mod 12,345,678

== Example of Non-Congruence Modulo an Integer ==
:$12 \, 345 \, 678 \, 987 \, 654 \, 321 \not \equiv 0 \pmod {12 \, 345 \, 678}$
== Proof ==
We have that $12 \, 345 \, 678$ ends in $8$.
Thus by Divisibility by 2, $12 \, 345 \, 678$ has $2$ as a divisor.
But $12 \, 345 \, 678 \, 987 \, 654 \, 321$ ends in $1$.
Thus, also by Divisibility by 2, $12 \, 345 \, 678 \, 987 \, 654 \, 321$ does not have $2$ as a divisor.
By Divisor Relation is Transitive, it follows that $12 \, 345 \, 678$ is not a divisor of $12 \, 345 \, 678 \, 987 \, 654 \, 321$.
The result follows by definition of congruence and divisibility.
== Sources ==
* : $\text {4-1}$ Basic Properties of Congruences: Exercise $7 \ \text{(a)}$
Category:Examples of Congruence Modulo Integer
Congruence Modulo Integer/Examples/12321 equiv 111 mod 3

== Example of Congruence Modulo an Integer ==
:$12 \, 321 \equiv 111 \pmod 3$
== Proof ==
By definition of congruence:
:$x \equiv y \pmod n$ $x - y = k n$
for some $k \in \Z$.
We have:
:$12 \, 321 - 111 = 12 \, 210$
The digit sum of $12 \, 210$ is $3$.
By Divisibility by 3, it follows that:
:$12 \, 210 = k \times 3$
for some $k \in \Z$.
The result follows by definition of congruence.
== Sources ==
* : $\text {4-1}$ Basic Properties of Congruences: Exercise $7 \ \text{(e)}$
Category:Examples of Congruence Modulo Integer
Category:12,321
Category:111
Congruence Modulo Integer/Examples/12 equiv 0 mod 3

== Example of Congruence Modulo an Integer ==
:$12 \equiv 0 \pmod 3$
== Proof ==
By definition of congruence:
:$x \equiv y \pmod n$ $x - y = k n$
for some $k \in \Z$.
We have:
:$12 - 0 = 12 = 4 \times 3$
Thus:
:$12 \equiv 0 \pmod 3$
== Sources ==
* : Chapter $\text {I}$: The Group Concept: $\S 6$: Examples of Finite Groups: $\text{(iii)}$
Category:Examples of Congruence Modulo Integer
Congruence Modulo Integer/Examples/13 equiv 3 mod 5

== Example of Congruence Modulo an Integer ==
:$13 \equiv 3 \pmod 5$
== Proof ==
By definition of congruence:
:$x \equiv y \pmod n$ $x - y = k n$
for some $k \in \Z$.
We have:
:$13 - 3 = 10 = 2 \times 5$
Thus:
:$13 \equiv 3 \pmod 5$
== Sources ==
* : $\S 2.5$. Congruence of integers: Example $38$
Category:Examples of Congruence Modulo Integer
Congruence Modulo Integer/Examples/17 equiv 12 mod 5

== Example of Congruence Modulo an Integer ==
:$17 \equiv 12 \pmod 5$
== Proof ==
By definition of congruence:
:$x \equiv y \pmod n$ $x - y = k n$
for some $k \in \Z$.
We have:
:$17 - 12 = 5 = 1 \times 5$
Thus:
:$17 \equiv 12 \pmod 5$
== Sources ==
* : $\text {4-1}$ Basic Properties of Congruences: Example $\text {4-1}$
Category:Examples of Congruence Modulo Integer
Congruence Modulo Integer/Examples/2 equiv -6 mod 4

== Example of Congruence Modulo an Integer ==
:$2 \equiv -6 \pmod 4$
== Proof ==
By definition of congruence:
:$x \equiv y \pmod n$ $x - y = k n$
for some $k \in \Z$.
We have:
:$2 - \paren {-6} = 8 = 2 \times 4$
Thus:
:$2 \equiv -6 \pmod 4$
== Sources ==
* : Chapter $1$: Integral Domains: $\S 6$. The Residue Classes: Example $8$
Category:Examples of Congruence Modulo Integer
Congruence Modulo Integer/Examples/3 equiv 15 mod 4

== Example of Congruence Modulo an Integer ==
:$3 \equiv 15 \pmod 4$
== Proof ==
By definition of congruence:
:$x \equiv y \pmod n$ $x - y = k n$
for some $k \in \Z$.
We have:
:$3 - 15 = -12 = \paren {-3} \times 4$
Thus:
:$3 \equiv 15 \pmod 4$
== Sources ==
* : Chapter $1$: Integral Domains: $\S 6$. The Residue Classes: Example $8$
Category:Examples of Congruence Modulo Integer
Congruence Modulo Integer/Examples/3 equiv 18 mod 5

== Example of Congruence Modulo an Integer ==
:$3 \equiv 18 \pmod 5$
== Proof ==
By definition of congruence:
:$x \equiv y \pmod n$ $x - y = k n$
for some $k \in \Z$.
We have:
:$3 - 18 = -15 = \paren {-3} \times 5$
Thus:
:$3 \equiv 18 \pmod 5$
== Sources ==
* : Chapter $\text {I}$: The Group Concept: $\S 6$: Examples of Finite Groups: $\text{(iii)}$
Category:Examples of Congruence Modulo Integer
Congruence Modulo Integer/Examples/531 not equiv 1236 mod 7561

== Example of Non-Congruence Modulo an Integer ==
:$531 \not \equiv 1236 \pmod {7561}$
== Proof ==
 $531 \equiv 1236 \pmod {7561}$.
We have that:
From Congruent Integers less than Half Modulus are Equal, it follows that $531 = 1236$.
The result follows by Proof by Contradiction.
== Sources ==
* : $\text {4-1}$ Basic Properties of Congruences: Exercise $7 \ \text{(d)}$
Category:Examples of Congruence Modulo Integer
Congruence Modulo Integer/Examples/57 not equiv 208 mod 4

== Example of Non-Congruence Modulo an Integer ==
:$57 \not \equiv 208 \pmod 4$
== Proof ==
By definition of congruence:
:$x \equiv y \pmod n$ $x - y = k n$
for some $k \in \Z$.
We have:
:$208 - 57 = 151 = 37 \times 4 + 3$
and so $208 - 57$ is not of the form $k \times 4$ for some $k \in \Z$.
Thus:
:$57 \not \equiv 208 \pmod 4$
== Sources ==
* : $\text {4-1}$ Basic Properties of Congruences: Exercise $7 \ \text{(c)}$
Category:Examples of Congruence Modulo Integer
Congruence Modulo Integer/Examples/8 equiv 2 mod 2

== Example of Congruence Modulo an Integer ==
:$8 \equiv 2 \pmod 2$
== Proof ==
By definition of congruence:
:$x \equiv y \pmod n$ $x - y = k n$
for some $k \in \Z$.
We have:
:$8 - 2 = 6 = 3 \times 2$
Thus:
:$8 \equiv 2 \pmod 2$
== Sources ==
* : $\text {4-1}$ Basic Properties of Congruences: Example $\text {4-1}$
Category:Examples of Congruence Modulo Integer
Congruence Modulo Integer/Examples/8 not equiv 3 mod 2

== Example of Non-Congruence Modulo an Integer ==
:$8 \not \equiv 3 \pmod 2$
== Proof ==
By definition of congruence:
:$x \equiv y \pmod n$ $x - y = k n$
for some $k \in \Z$.
We have:
:$8 - 3 = 5 = 2 \times 2 + 1 = 2 \cdotp 5 \times 2$
and so $8 - 3$ is not of the form $k \times 2$ for some $k \in \Z$.
Thus:
:$8 \not \equiv 3 \pmod 2$
== Sources ==
* : $\text {4-1}$ Basic Properties of Congruences: Example $\text {4-1}$
Category:Examples of Congruence Modulo Integer
Congruence Modulo Integer is Equivalence Relation

== Theorem ==
For all $z \in \Z$, congruence modulo $z$ is an equivalence relation.
== Proof ==
Checking in turn each of the criteria for equivalence:
=== Reflexive ===
We have that Equal Numbers are Congruent:
:$\forall x, y, z \in \Z: x = y \implies x \equiv y \pmod z$
so it follows that:
:$\forall x \in \Z: x \equiv x \pmod z$
and so congruence modulo $z$ is reflexive.
=== Symmetric ===
So congruence modulo $z$ is symmetric.
=== Transitive ===
So congruence modulo $z$ is transitive.
So we are justified in supposing that congruence, as we have defined it, is an equivalence.
== Sources ==
* : Chapter $\text {II}$: Topological Spaces: $\S 10$. Equivalence Relations
* : $\S 2.5$. Congruence of integers
* : Chapter $\text {II}$: New Structures from Old: $\S 11$: Quotient Structures: Example $11.2$
* : Chapter $\text{I}$: Sets and Functions: Relations
* : Appendix: Elementary set and number theory
* : Chapter $1$: Integral Domains: $\S 6$. The Residue Classes: Theorem $3$
* : Chapter $1$: Rings - Definitions and Examples: $2$: Some examples of rings: Ring Example $2$
* : $\text {4-1}$ Basic Properties of Congruences: Theorem $\text {4-1}$
* : $\S 6$. Indexed families; partitions; equivalence relations: Example $6.5$
* : Appendix $\text{A}.3$: Equivalence Relations: $(2)$
* : Appendix $\text{A}.3$: Equivalence Relations: Theorem $\text{A}.3$
* : $\S 14.1$: Congruence modulo $m$ ($m \in \N$)
* : $\S 16.1$: Equivalence relations
* : $\S 2.3$: Congruences: Theorem $1$
* : Appendix $1$: Some Results from the Elementary Theory of Numbers: Corollary $11$
* : Chapter $2$: Maps and relations on sets: Example $2.26$
* : Part $1$: Not Entirely Naive Set Theory: Chapter $1$: Pairs, Relations, and Functions
* 
* 
* 
Category:Congruence (Number Theory)
Category:Modulo Arithmetic
Category:Examples of Equivalence Relations
Congruence Modulo Normal Subgroup is Congruence Relation

== Theorem ==
Let $\struct {G, \circ}$ be a group.
Let $N$ be a normal subgroup of $G$.
Then congruence modulo $N$ is a congruence relation for the group operation $\circ$.
== Proof ==
Let $x \mathrel {\RR_N} y$ denote that $x$ and $y$ are in the same coset, that is:
:$x \mathrel {\RR_N} y \iff x \circ N = y \circ N$
as specified in the definition of congruence modulo $N$.
Let $x \mathrel {\RR_N} x'$ and $y \mathrel {\RR_N} y'$.
To demonstrate that $\RR_N$ is a congruence relation for $\circ$, we need to show that:
:$\paren {x \circ y} \mathrel {\RR_N} \paren {x' \circ y'}$
So:
By Cosets are Equal iff Product with Inverse in Subgroup:
:$x \circ x'^{-1} \in N$ and $y \circ y'^{-1} \in N$
Thus:
:$\paren {x \circ y} \circ \paren {x' \circ y'}^{-1} \in x \circ H \circ x'^{-1}$
But we also have that:
That is:
:$\paren {x \circ y} \circ \paren {x' \circ y'}^{-1} \in H$
and so:
:$\paren {x \circ y} \mathrel {\RR_N} \paren {x' \circ y'}$
Hence the result, by definition of congruence relation.
== Also see ==
* Congruence Relation induces Normal Subgroup, the converse of this result
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 11$: Quotient Structures: Theorem $11.3$
Category:Normal Subgroups
Category:Examples of Congruence Relations
Congruence Modulo Power of p as Linear Combination of Congruences Modulo p

== Theorem ==
Let $p$ be a prime number.
Let $S = \set {a_1, a_2, \ldots, a_p}$ be a complete residue system modulo $p$.
Then for all integers $n \in \Z$ and non-negative integer $s \in \Z_{\ge 0}$, there exists a congruence of the form:
:$n \equiv \ds \sum_{j \mathop = 0}^s b_j p^j \pmod {p^{s + 1} }$
where $b_j \in S$.
== Proof ==
Proof by induction on $s$:
=== Basis for the Induction ===
For $s = 0$, we apply the definition of a complete residue system modulo $p$:
:$\forall n \in \Z: \exists a_i \in S: n \equiv a_i \pmod p$
This is our base case.
=== Induction Hypothesis ===
This is our induction hypothesis:
:For some $k \in \Z_{\ge 0}$, for all integers $n \in \Z$, there exists a congruence of the form:
::$n \equiv \ds \sum_{j \mathop = 0}^k b_j p^j \pmod {p^{k + 1} }$
It is to be demonstrated that:
:For all integers $n \in \Z$, there exists a congruence of the form:
::$n \equiv \ds \sum_{j \mathop = 0}^{k + 1} b_j p^j \pmod {p^{k + 2} }$
=== Induction Step ===
This is our induction step:
From $n \equiv \ds \sum_{j \mathop = 0}^k b_j p^j \pmod {p^{k + 1} }$ we have:
:$\exists q \in \Z: n = \ds \sum_{j \mathop = 0}^k b_j p^j + q p^{k + 1}$
From the definition of a complete residue system modulo $p$:
:$\exists a_i \in S: q \equiv a_i \pmod p$
This gives:
:$\exists r \in \Z: q = a_i + r p$
Substituting this to the original equation we have:
This shows that $n$ can be expressed as the form:
:$n \equiv \ds \sum_{j \mathop = 0}^{k + 1} b_j p^j \pmod {p^{k + 2} }$
By the Principle of Mathematical Induction, the theorem is true for any $s$.
Note that in the proof above, we did not use the fact that $p$ is a prime number.
== Sources ==
* : $\text {4-2}$ Residue Systems: Exercise $3$
Category:Residue Classes
Category:Proofs by Induction
Congruence Modulo Real Number is Equivalence Relation

== Theorem ==
For all $z \in \R$, congruence modulo $z$ is an equivalence relation.
== Proof ==
Checking in turn each of the criteria for equivalence:
=== Reflexive ===
We have that Equal Numbers are Congruent:
:$\forall x, y, z \in \R: x = y \implies x \equiv y \pmod z$
so it follows that:
:$\forall x \in \R: x \equiv x \pmod z$
and so congruence modulo $z$ is reflexive.
=== Symmetric ===
So congruence modulo $z$ is symmetric.
=== Transitive ===
So congruence modulo $z$ is transitive.
So we are justified in supposing that congruence, as we have defined it, is an equivalence.
== Also see ==
* Congruence Modulo Integer is Equivalence Relation, in which context this result is usually encountered
== Sources ==
* : Chapter $1$: Theory of Sets: $\S 7$: Relations
Category:Modulo Arithmetic
Category:Examples of Equivalence Relations
Congruence Modulo Subgroup is Equivalence Relation

== Theorem ==
Let $G$ be a group, and let $H$ be a subgroup of $G$.
Let $x, y \in G$.
=== Left Congruence Modulo Subgroup is Equivalence Relation ===
=== Right Congruence Modulo Subgroup is Equivalence Relation ===
== Also see ==
* Definition:Coset
* Definition:Coset Space
== Sources ==
* : Chapter $5$: Rings: $\S 20$. Cosets: Theorem $33$
Category:Congruence Modulo Subgroup
Category:Examples of Equivalence Relations
Congruence Modulo Zero is Diagonal Relation

== Theorem ==
Congruence modulo zero is the diagonal relation.
That is:
:$x \equiv y \pmod 0 \iff x = y$
== Proof ==
Follows directly from the definition of congruence:
:$x \equiv y \pmod z \iff x \bmod z = y \bmod z$ 
When $z = 0$ we have by definition:
:$x \bmod 0 := x$
And so $x \bmod 0 = y \bmod 0 \iff x = y$.
Hence the result.
Category:Modulo Arithmetic
Congruence Modulo a Principal Ideal of P-adic Integers

== Theorem ==
Let $\struct {\Q_p, \norm {\,\cdot\,}_p}$ be the $p$-adic numbers for some prime $p$.
Let $\Z_p$ be the $p$-adic integers.
For any $\epsilon \in \R_{>0}$ and $a \in \Q_p$ let $\map B a$ denote the open ball of center $a$ of radius $\epsilon$. 
For any $\epsilon \in \R_{>0}$ and $a \in \Q_p$ let $\map { {B_\epsilon}^-} a$ denote the closed ball of center $a$ of radius $\epsilon$. 
For any $a \in \Z_p$ and $n \in \N$ let $a + p^n\Z_p$ denote the coset of $a$ modulo $p^n\Z_p$. 
For any $a, b \in \Z_p$ and $n \in \N$ let $x \equiv y \pmod{p^n \Z_p}$ denote congruence modulo the principal ideal $p^n\Z_p$.
Let $x, y \in \Z_p$.
Let $k \in \N$.
::$(1)\quad x \equiv y \pmod{p^{k+1} \Z_p}$
::$(2)\quad x \in y + p^{k+1} \Z_p$
::$(3)\quad x + p^{k+1} \Z_p = y + p^{k+1} \Z_p$
::$(4)\quad x \in \map {B_{p^{-k}}} y$
::$(5)\quad \norm{x - y}_p < p^{-k}$
::$(6)\quad \map {B_{p^{-k}}} x = \map {B_{p^{-k}}} y$
::$(7)\quad x \in \map {B^{\,-}_{p^{-k-1}}} y$
::$(8)\quad \norm{x - y}_p \le p^{-k-1}$
::$(9)\quad \map {B^{\,-}_{p^{-k-1}}} x = \map {B^{\,-}_{p^{-k-1}}} y$
== Proof ==
=== Condition (1) is Equivalent to Condition (3) ===
We have:
=== Conditions (2), (3), (4), (5) and (6) are equivalent ===
Follows directly from Characterization of Open Ball in P-adic Numbers.
=== Conditions (2), (7), (8) and (9) are equivalent ===
Follows directly from Characterization of Closed Ball in P-adic Numbers.
Category:P-adic Integers
Congruence Relation/Examples

== Examples of Congruence Relations ==
=== Equal Fourth Powers over $\C$ for Multiplication ===
=== Equal Fourth Powers over $\C$ for Addition ===
=== $\sin \dfrac {\pi x} 6 = \sin \dfrac {\pi y} 6$ over $\Z$ for Multiplication ===
=== $\sin \dfrac {\pi x} 6 = \sin \dfrac {\pi y} 6$ over $\Z$ for Addition ===
Category:Examples of Congruence Relations
Congruence Relation/Examples/Equal Fourth Powers over Complex Numbers for Addition

== Example of Congruence Relation ==
Let $\C$ denote the set of complex numbers.
Let $\RR$ denote the equivalence relation on $\C$ defined as:
:$\forall w, z \in \C: z \mathrel \RR w \iff z^4 = w^4$
Then $\RR$ is not a congruence relation for addition on $\C$.
== Proof ==
;Proof by Counterexample
We have from Equivalence Relation Examples: Equal Fourth Powers over Complex Numbers, $\RR$ is an equivalence relation.
However:
But:
:$\paren {i + -i}^4 = 0$
while:
:$\paren {i + 1}^4 = -4$
So while we have:
:$\paren {w_1 \mathrel \RR w_2} \land \paren {z_1 \mathrel \RR z_2}$
where $w_1 = i$, $w_2 = 1$, $z_1 = -i$, $z_2 = -i$
we have:
:$\paren {w_1 + z_1} \not \mathrel \RR \paren {w_2 + z_2}$
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 11$: Quotient Structures: Exercise $11.1 \ \text{(a)}$
Category:Examples of Congruence Relations
Congruence Relation/Examples/Equal Fourth Powers over Complex Numbers for Multiplication

== Example of Congruence Relation ==
Let $\C$ denote the set of complex numbers.
Let $\RR$ denote the equivalence relation on $\C$ defined as:
:$\forall w, z \in \C: z \mathrel \RR w \iff z^4 = w^4$
Then $\RR$ is a congruence relation for multiplication on $\C$.
== Proof ==
Note that by Equivalence Relation Examples: Equal Fourth Powers over Complex Numbers, $\RR$ is an equivalence relation.
It remains to be shown that it is a congruence.
Let $w_1, w_2, z_1, z_2 \in \C$ such that:
:$\paren {w_1 \mathrel \RR z_1} \land \paren {z_1 \mathrel \RR z_2}$
Then:
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 11$: Quotient Structures: Exercise $11.1 \ \text{(a)}$
Category:Examples of Congruence Relations
Congruence Relation/Examples/Equal Sine of pi x over 6 on Integers for Addition

== 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 addition 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 + 2} \pi} 6 = 1$
while:
:$\sin \dfrac {\paren {4 + 5} \pi} 6 = -1$
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 = 2$, $y_2 = 4$
we have:
:$\paren {x_1 + y_1} \not \mathrel \RR \paren {x_2 + y_2}$
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 11$: Quotient Structures: Exercise $11.1 \ \text{(b)}$
Category:Examples of Congruence Relations