Editing Congruence relation (section)

== Examples ==

=== Basic example ===
{{About|the ''(mod'' n'')'' notation|the binary ''mod'' operation|modulo operation|section=yes}}

The prototypical example of a congruence relation is [[Modular arithmetic#Congruence|congruence modulo]] <math>n</math> on the set of [[integer]]s.  For a given positive integer <math>n</math>, two integers <math>a</math> and <math>b</math> are called '''congruent modulo <math>n</math>''', written
: <math>a \equiv b \pmod{n}</math>
if <math>a - b</math> is [[divisible]] by <math>n</math> (or equivalently if <math>a</math> and <math>b</math> have the same [[remainder]] when divided by <math>n</math>).

For example, <math>37</math> and <math>57</math> are congruent modulo <math>10</math>,
: <math>37 \equiv 57 \pmod{10}</math>
since <math>37 - 57 = -20</math> is a multiple of 10, or equivalently since both <math>37</math> and <math>57</math> have a remainder of <math>7</math> when divided by <math>10</math>.

Congruence modulo <math>n</math> (for a fixed <math>n</math>) is compatible with both [[addition]] and [[multiplication]] on the integers.  That is,

if
: <math>a_1 \equiv a_2 \pmod{n} </math> and <math> b_1 \equiv b_2 \pmod{n}</math> 
then
: <math>a_1 + b_1 \equiv a_2 + b_2 \pmod{n} </math>  and  <math> a_1 b_1 \equiv a_2b_2 \pmod{n}</math>

The corresponding addition and multiplication of equivalence classes is known as [[modular arithmetic]].  From the point of view of abstract algebra, congruence modulo <math>n</math> is a congruence relation on the [[ring (mathematics)|ring]] of integers, and arithmetic modulo <math>n</math> occurs on the corresponding [[quotient ring]].

=== Example: Groups ===
For example, a group is an algebraic object consisting of a [[set (mathematics)|set]] together with a single [[binary operation]], satisfying certain axioms.  If <math>G</math> is a group with operation <math>\ast</math>, a '''congruence relation''' on <math>G</math> is an equivalence relation <math>\equiv</math> on the elements of <math>G</math> satisfying
:<math>g_1 \equiv g_2 \ \ \,</math> and <math>\ \ \, h_1 \equiv h_2 \implies g_1 \ast h_1 \equiv g_2 \ast h_2</math> 
for all <math>g_1, g_2, h_1, h_2 \in G</math>. For a congruence on a group, the equivalence class containing the [[identity element]] is always a [[normal subgroup]], and the other equivalence classes are the other [[coset]]s of this subgroup.  Together, these equivalence classes are the elements of a [[quotient group]].

=== Example: Rings ===
When an algebraic structure includes more than one operation, congruence relations are required to be compatible with each operation.  For example, a ring possesses both addition and multiplication, and a congruence relation on a ring must satisfy
: <math>r_1 + s_1 \equiv r_2 + s_2</math> and <math>r_1 s_1 \equiv r_2 s_2</math>
whenever <math>r_1 \equiv r_2</math> and <math>s_1 \equiv s_2</math>. For a congruence on a ring, the equivalence class containing 0 is always a two-sided [[ideal (ring theory)|ideal]], and the two operations on the set of equivalence classes define the corresponding quotient ring.