Fact-checked by Grok 2 weeks ago

Congruence relation

In mathematics, a congruence relation, also known as a congruence, is an equivalence relation defined on the carrier set of an algebraic structure that is compatible with the structure's operations, meaning it preserves the results of those operations when applied to equivalent elements.^[1] This compatibility ensures that if elements a_1 \equiv b_1, \dots, a_n \equiv b_n under the congruence, then for any n-ary operation f of the algebra, f(a_1, \dots, a_n) \equiv f(b_1, \dots, b_n).^[2] Congruences generalize the familiar notion of congruence modulo n on the integers, where two integers a and b are congruent modulo a positive integer n, denoted a \equiv b \pmod{n}, if n divides a - b, partitioning the integers into equivalence classes known as residue classes.^[3] As an equivalence relation, every congruence satisfies reflexivity (a \equiv a), symmetry (if a \equiv b then b \equiv a), and transitivity (if a \equiv b and b \equiv c then a \equiv c).^[3] In the context of universal algebra, congruences enable the construction of quotient algebras, where the equivalence classes serve as the new carrier set, and operations are defined naturally on these classes via a canonical surjective homomorphism.^[1] The set of all congruences on a given algebra forms a complete lattice under inclusion, ordered by refinement, which facilitates the study of algebraic varieties and homomorphic images.^[1] Congruence relations appear prominently in various algebraic domains: in group theory, they correspond to normal subgroups, yielding quotient groups; in ring theory, they align with ideals, producing quotient rings; and in lattice theory or order theory, they respect partial orders or meets and joins.^[1] For instance, in the integers under addition and multiplication, the principal congruence modulo n is generated by the pairs (kn, 0) for integers k, forming the ring of integers modulo n, \mathbb{Z}/n\mathbb{Z}.^[1] These relations are fundamental to solving linear congruences, analyzing Diophantine equations, and understanding modular arithmetic, with applications extending to cryptography, coding theory, and computational number theory.^[3]

Core Concepts

Definition

In universal algebra, a congruence relation on an algebra A of type F is defined as an equivalence relation \theta on the carrier set (universe) A that satisfies a compatibility condition with respect to the operations specified by F.^[4] Formally, \theta is a congruence if, for every n-ary operation symbol f \in F and all tuples (a_1, \dots, a_n), (b_1, \dots, b_n) \in A^n such that a_i \theta b_i for each i = 1, \dots, n, it holds that

f_A(a_1, \dots, a_n) \theta f_A(b_1, \dots, a_n),

where f_A denotes the interpretation of f in A. This compatibility property ensures that the algebraic structure is preserved under the equivalence.^[4] For binary operations, such as a multiplication * on A, the condition specializes to: if a \theta a' and b \theta b', then a * b \theta a' * b'. Congruences are typically denoted by \theta or \sim, distinguishing them from arbitrary equivalence relations by their structure-preserving nature, which allows the formation of well-defined quotient algebras A/\theta.^[4]

Properties

A congruence relation on an algebra is fundamentally an equivalence relation, meaning it satisfies the properties of reflexivity, symmetry, and transitivity.^[5]^[6] The congruence classes induced by a congruence \theta on A are the sets _\theta = \{ b \in A \mid (a, b) \in \theta \}, which partition A. Specifically, for any operation f of arity n and elements a_1, \dots, a_n \in A, if each a_i \in [b_i]_\theta, then f(a_1, \dots, a_n) \in [f(b_1, \dots, b_n)]_\theta. This ensures that operations are well-defined on the quotient set.^[5]^[6] The quotient set A / \theta, consisting of these congruence classes, inherits the structure of an algebra with operations defined componentwise: for an n-ary operation f, the induced operation is f_{A/\theta}([a_1]_\theta, \dots, [a_n]_\theta) = [f(a_1, \dots, a_n)]_\theta. This well-definedness follows from the compatibility condition, and the quotient algebra A / \theta satisfies all equations that A does, preserving the variety of the original algebra. The canonical projection \pi_\theta: A \to A / \theta is a homomorphism witnessing this structure.^[5]^[6] The collection of all congruences on an algebra A, denoted \mathrm{Con}(A), ordered by inclusion, forms a complete lattice. The meet of any family of congruences is their intersection, which is again a congruence as it inherits compatibility and equivalence properties. The join is the congruence generated by the union, obtained via the transitive closure under relational products, ensuring \mathrm{Con}(A) is closed under arbitrary infima and suprema. The trivial congruence \Delta_A = \{(a,a) \mid a \in A\} (the equality relation) is the least element, and the full relation \nabla_A = A \times A is the greatest. This lattice structure is algebraic, with compact elements corresponding to finitely generated congruences.^[5]^[6]

Examples

Modular Arithmetic

A fundamental example of a congruence relation arises in the integers \mathbb{Z} under the relation of congruence modulo n, where n is a positive integer. Two integers a and b are congruent modulo n, denoted a \equiv b \pmod{n}, if and only if n divides a - b, meaning there exists an integer k such that a - b = kn.^[7]^[8] This relation partitions the integers into equivalence classes known as residue classes. The residue class of an integer a modulo n consists of all integers that differ from a by multiples of n, formally = \{ \dots, a - 2n, a - n, a, a + n, a + 2n, \dots \}.^[7]^[9] The congruence relation modulo n is compatible with the operations of addition and multiplication on the integers. Specifically, if a \equiv b \pmod{[n](/page/N+)} and c \equiv d \pmod{[n](/page/N+)}, then a + c \equiv b + d \pmod{[n](/page/N+)} and ac \equiv [bd](/page/BD) \pmod{[n](/page/N+)}.^[7] This compatibility ensures that the set of residue classes forms a ring under the induced operations, denoted \mathbb{Z}/[n](/page/N+)\mathbb{Z}, where addition and multiplication are performed modulo [n](/page/N+).^[7] In this quotient ring, each element is a residue class, and the structure captures the arithmetic of integers "wrapped around" every [n](/page/N+) units.^[9] The concept of congruence modulo n was introduced by Carl Friedrich Gauss in his 1801 work Disquisitiones Arithmeticae, where he developed it as a tool for investigating properties of integers and Diophantine equations.^[10]^[11]

Groups

In group theory, a congruence relation on a group G is an equivalence relation \sim that respects the group operation, meaning if g_1 \sim h_1 and g_2 \sim h_2, then g_1 g_2 \sim h_1 h_2. Such relations on groups are in one-to-one correspondence with the normal subgroups of G. Specifically, every normal subgroup N \trianglelefteq G determines a congruence via g \sim h if and only if g^{-1} h \in N, and conversely, every congruence arises this way from the normal subgroup consisting of elements equivalent to the identity.$$] ^[2]^[12] The equivalence classes for this congruence are the left cosets of N in G, denoted gN = \{gn \mid n \in N\} for g \in G. These cosets partition G and form a group structure under the induced operation (gN)(hN) = (gh)N, which is well-defined because N is normal (ensuring that the product of cosets depends only on the cosets themselves, not on choices of representatives). This group is called the quotient group G/N, with identity coset N and inverse (gN)^{-1} = g^{-1}N.[$$ ^[13]^[14] Two prominent examples illustrate this construction. The trivial congruence corresponds to N = G, the entire group as a normal subgroup, where every element is equivalent to every other, yielding a single coset G and the trivial quotient group \{G\} with one element. The discrete congruence arises from N = \{e\}, the trivial subgroup (which is always normal), where g \sim h holds only if g = h, so the cosets are singletons \{g\} and the quotient G/\{e\} \cong G is isomorphic to the original group.$$] ^[2]^[12] Importantly, not every subgroup of G induces a congruence relation; only normal subgroups do, as non-normal subgroups fail to produce an equivalence that is compatible with the group multiplication (the induced relation would not satisfy the compatibility condition for all pairs of elements).[$$ ^[2]^[1]

Rings

In ring theory, a congruence relation on a ring R is determined by an ideal I of R, where two elements a, b \in R satisfy a \sim b if and only if a - b \in I.^[15] This relation is an equivalence relation because I is an additive subgroup of R, ensuring reflexivity, symmetry, and transitivity, while the ideal property guarantees compatibility with the ring operations.^[16] The equivalence classes under this congruence are the left (or right, since ideals are two-sided) cosets of I in R, denoted a + I = \{a + i \mid i \in I\}.^[15] These cosets form the quotient ring R/I, equipped with well-defined addition and multiplication: (a + I) + (b + I) = (a + b) + I and (a + I)(b + I) = ab + I.^[16] The operations are well-defined precisely because I absorbs multiplication by elements of R, preventing ambiguity in representatives./16:_Rings/16.05:_Ring_Homomorphisms_and_Ideals) A concrete example arises in polynomial rings: the quotient \mathbb{R}/(x^2 + 1)\mathbb{R} is isomorphic to the field of complex numbers \mathbb{C}, where the isomorphism sends the coset of x to i = \sqrt{-1}, allowing polynomials to be reduced modulo x^2 + 1 to linear forms a + bi with a, b \in \mathbb{R}.^[17] More generally, every ideal I of a ring R serves as the kernel of the canonical projection homomorphism \pi: R \to R/I, and conversely, the kernel of any ring homomorphism is an ideal./16:_Rings/16.05:_Ring_Homomorphisms_and_Ideals) This correspondence underscores the role of congruences in constructing quotient structures that preserve ring operations.^[18]

Structural Connections

Homomorphisms

In universal algebra, the kernel of a homomorphism \phi: A \to B between two algebras over the same signature is defined as the relation \ker(\phi) = \{(a, b) \in A \times A \mid \phi(a) = \phi(b)\}. This kernel is always a congruence on A, as it forms an equivalence relation—reflexive because \phi(a) = \phi(a), symmetric because equality is symmetric, and transitive because if \phi(a) = \phi(b) and \phi(b) = \phi(c), then \phi(a) = \phi(c)—and it is compatible with the operations of A: if (a_i, b_i) \in \ker(\phi) for i = 1, \dots, n, then \phi(f_A(a_1, \dots, a_n)) = f_B(\phi(a_1), \dots, \phi(a_n)) = f_B(\phi(b_1), \dots, \phi(b_n)) = \phi(f_A(b_1, \dots, b_n)), so (f_A(a_1, \dots, a_n), f_A(b_1, \dots, b_n)) \in \ker(\phi).^[5] The first isomorphism theorem establishes a fundamental connection between this kernel and quotient structures: the quotient algebra A / \ker(\phi) is isomorphic to the image \operatorname{im}(\phi) = \{\phi(a) \mid a \in A\}, where the isomorphism is given by the map _{\ker(\phi)} \mapsto \phi(a). This map is well-defined because if _{\ker(\phi)} = [a']_{\ker(\phi)}, then (a, a') \in \ker(\phi), so \phi(a) = \phi(a'); it is bijective, with inverse \phi(a) \mapsto _{\ker(\phi)}; and it preserves operations since \phi is a homomorphism.^[5] Conversely, every congruence \theta on A arises as the kernel of some homomorphism, specifically the natural projection \pi: A \to A / \theta defined by \pi(a) = _\theta. Here, \ker(\pi) = \theta because \pi(a) = \pi(b) if and only if (a, b) \in \theta, and \pi is a surjective homomorphism that preserves all operations by the definition of the quotient algebra.^[5] A concrete example occurs in the context of modular arithmetic on the integers: the projection homomorphism \pi: \mathbb{Z} \to \mathbb{Z}/n\mathbb{Z} given by \pi(k) = k \mod n has kernel \ker(\pi) = \{(a, b) \in \mathbb{Z} \times \mathbb{Z} \mid a \equiv b \pmod{n}\}, which is precisely the standard congruence relation modulo n. By the first isomorphism theorem, \mathbb{Z} / \ker(\pi) \cong \mathbb{Z}/n\mathbb{Z}.^[5]

Normal Subgroups and Ideals

In group theory, a congruence relation on a group G is determined by a normal subgroup N \trianglelefteq G, where two elements g_1, g_2 \in G are congruent modulo N if g_1 g_2^{-1} \in N (or equivalently, g_1^{-1} g_2 \in N), and the congruence classes are the cosets of N. This equivalence relation preserves the group operation because N is normal, ensuring that the quotient set G/N forms a group under the induced operation. A subgroup N of G is normal if and only if it is the kernel of some group homomorphism \phi: G \to H, where the kernel is defined as \ker \phi = \{ g \in G \mid \phi(g) = e_H \}. This correspondence establishes a bijection between the normal subgroups of G and the congruence relations on G.^[2]/02%3A_Groups/2.04%3A_Group_homomorphisms) An equivalent characterization of normality is that N is invariant under conjugation: g N g^{-1} = N for all g \in G. This condition ensures that left and right cosets coincide, gN = Ng, which is necessary for the coset partition to define a congruence compatible with the group multiplication. The kernel property follows directly from this invariance, as homomorphisms preserve the group structure, and conversely, for any normal subgroup N, the canonical projection \pi: G \to G/N is a surjective homomorphism with kernel N. Thus, normal subgroups unify the notions of kernels and congruences in groups.^[19] In ring theory, congruence relations on a ring R correspond precisely to two-sided ideals I of R, where a \equiv b \pmod{I} if a - b \in I, and the classes a + I form the quotient ring R/I. A subset I of R is a two-sided ideal if it absorbs multiplication from both sides: for all r \in R and i \in I, r i \in I and i r \in I. Such an ideal I is the kernel of a ring homomorphism \psi: R \to S if and only if it is two-sided, as the homomorphism must preserve both addition and multiplication, requiring the kernel to be compatible with left and right multiplications. Left ideals (absorbing only right multiplication) and right ideals (absorbing only left multiplication) do not generally yield ring congruences unless the ring is commutative, but in the general case, two-sided ideals provide the full correspondence. This bijection between two-sided ideals and congruences mirrors the group case, enabling quotient constructions.^[15]^[20] In the setting of universal algebra, congruences on an algebra A in a variety are exactly the kernels of homomorphisms from A to other algebras in the variety, where the kernel is the equivalence relation \theta = \{ (a, b) \in A \times A \mid \phi(a) = \phi(b) \} for some \phi: A \to B. These kernels are fully invariant under endomorphisms of A, meaning that if (a, b) \in \theta, then (\phi(a), \phi(b)) \in \theta for any endomorphism \phi. The lattice of congruences \mathrm{Con}(A) is algebraic and complete, with a bijection to the closed fully invariant subsets via the term condition or the quotient algebras A/\theta. This general framework encompasses groups and rings as special cases, where normal subgroups and two-sided ideals are the specific fully invariant congruence kernels.^[21]

General Frameworks

Universal Algebra

In universal algebra, a congruence relation on an algebra A with a given signature of operations is defined as an equivalence relation \theta on the carrier set of A that is compatible with all the operations, meaning it preserves the algebraic structure under substitution: if a_i \theta b_i for all i < n_f, then f(a_0, \dots, a_{n_f-1}) \theta f(b_0, \dots, b_{n_f-1}) for every operation f of arity n_f. This extends the notion to arbitrary algebraic structures, including those with relations if the signature incorporates them, ensuring the quotient A/\theta forms an algebra of the same type. The set \operatorname{Con}(A) of all congruences on an algebra A, ordered by inclusion, forms a complete algebraic lattice, where the meet of congruences is their intersection and the join is the smallest congruence containing their union. This lattice structure captures the hierarchical organization of equivalence classes compatible with the algebra's operations, with the trivial congruences \Delta_A (the equality relation) as the bottom element and \nabla_A (the full relation) as the top. In varieties of algebras—equational classes closed under homomorphic images, subalgebras, and products—specific properties of \operatorname{Con}(A) arise; for instance, a variety is congruence-permutable if congruences \theta and \phi satisfy \theta \circ \phi = \phi \circ \theta for all algebras in the variety, a condition equivalent to the existence of a Mal'cev term m(x,y,z) such that m(x,x,y) \approx y and m(x,y,y) \approx x, as in the variety of groups where normal subgroups ensure permutability. Similarly, a variety is congruence-distributive if \operatorname{Con}(A) is distributive for every A in the variety, characterized by primal algebras or discriminator terms, as exemplified by the variety of lattices where congruences correspond to filters and ideals. Principal congruences play a central role in generating \operatorname{Con}(A), with \theta(a,b) denoting the smallest congruence on A such that a \theta(a,b) b, obtained as the transitive closure of the relation generated by substituting polynomials or algebraic functions that identify a and b. These are finitely generated and compact in the lattice, allowing every congruence to be expressed as a join of principal ones in algebraic lattices. The HSP theorem, fundamental to varieties, states that a class of algebras is a variety if and only if it is closed under the operators H (homomorphic images, via congruences), S (subalgebras), and P (arbitrary products), implying that varieties are precisely the HSP-closures of their subdirectly irreducible members and enabling the representation of any algebra as a subdirect product of simples modulo principal congruences.

Category Theory

In category theory, particularly in categories equipped with pullbacks, a congruence on an object A is defined as an internal equivalence relation, represented by a subobject R \hookrightarrow A \times A equipped with structure maps ensuring reflexivity, symmetry, and transitivity. This subobject gives rise to a pair of parallel arrows (p_1, p_2): R \rightrightarrows A, where p_1 and p_2 are the projections from R to A. The coequalizer of this pair, denoted q: A \to A/\sim, exists in such categories and yields the quotient object A/\sim, where \sim denotes the equivalence relation induced by the congruence.^[22] The quotient object satisfies a universal property: for any morphism h: A \to B that coequalizes the pair (p_1, p_2)—meaning h \circ p_1 = h \circ p_2—there exists a unique morphism \overline{h}: A/\sim \to B such that h = \overline{h} \circ q. This property characterizes the coequalizer and ensures that homomorphisms from A respecting the congruence factor uniquely through the quotient. A congruence is effective if it is the kernel pair of its coequalizer morphism q, meaning the pair (p_1, p_2) is precisely the pullback of q along itself.^[23] In the category \mathbf{Set}, congruences correspond exactly to ordinary equivalence relations on sets, with the coequalizer q: A \to A/\sim being the canonical surjection onto the set of equivalence classes, and the universal property reducing to the standard fact that functions constant on equivalence classes descend to the quotient set.^[23] In abelian categories, kernels of morphisms are normal monomorphisms, as every monomorphism is the kernel of its cokernel, providing a canonical way to construct normal subobjects. Congruences in this setting manifest as effective equivalence relations, where the kernel pair of any morphism forms a congruence, and the coequalizer yields the corresponding quotient, aligning with the exact structure of the category.^[24]

References

[1]
[PDF] Math 222A W03 D. Congruence relations 1. The concept 2. Examples
1.1 Definition. A congruence relation on an algebra A = hA; f1,...,fmi is an. equivalence relation ≡ that is compatible with the operations, in the sense.
[2]
[PDF] Math 222A W03 D. Congruence relations 1 . The concept Let's start ...
The same definition works for algebraic systems in general: 1 . 1 Definition. A congruence relation on an algebra A = (A; /i, . . . , / m) is an.
[3]
3.1 Congruence
If n is a positive integer, we say the integers a and b are congruent modulo n, and write a≡b(modn), if they have the same remainder on division by n.
[4]
[PDF] A Course in Universal Algebra
The original 1981 edition of A Course in Universal Algebra has now been. LaTeXed, so the authors could make the out-of-print Springer-Verlag Grad-.
[5]
[PDF] A Course in Universal Algebra
We predict that such “applied universal algebra” will become much more prominent. ... An algebra A has the congruence extension property (CEP) if for every B ≤ A ...
[6]
[PDF] Lectures on Universal Algebra
Nov 8, 1999 · Definition 6 A binary relation θ on an algebra A is called a congruence relation on A if it is an equivalence relation on A which is compatible ...
[7]
Congruence -- from Wolfram MathWorld
Congruences also have their limitations. For example, if a=b and c=d (mod n) , then it follows that a^x=b^x , but usually not that x^c=x^d or a^c=b^d . In ...
[8]
3.1: Modulo Operation - Mathematics LibreTexts
May 19, 2022 · Two integers a and b are said to be congruent modulo n , a ≡ b ⁡ ( m ⁢ o ⁢ d n ) , if all of the following are true: a) ...
[9]
7.4: Modular Arithmetic - Mathematics LibreTexts
Sep 29, 2021 · The set of congruence classes for the relation of congruence modulo n on Z is the set of integers modulo n , or the set of integers mod n .The Integers Modulo n · Definition: integers modulo n · Theorem 3.28 · Definition
[10]
Disquisitiones Arithmeticae | Carl Friedrich GAUSS | First edition
He introduced congruence of integers with respect to a modulus (a ≡ b (mod c) if c divides a - b), the first significant algebraic example of the now ubiquitous ...
[11]
Disquisitiones arithmeticae : Gauss, Carl Friedrich, 1777-1855
Aug 11, 2018 · Publication date: 1801. Topics: Number theory. Publisher: Lipsiae : In commiss. apud Gerh. Fleischer, jun. Collection: smithsonian.Missing: congruence relation
[12]
[PDF] Introduction to Algebra - UC Berkeley math
Mar 7, 2019 · Exercise 69 Prove that any congruence ∼ on a group G is of the form ∼N for some normal subgroup N ⊆ G. 4.5.8 Notation for normal subgroups. The ...
[13]
[PDF] 6 Normal Subgroups and Quotient Groups - MIT OpenCourseWare
The quotient group G/N is the set of cosets of a normal subgroup N. The ... This is one of the most basic operations we can do on groups! Proof. First ...<|control11|><|separator|>
[14]
[PDF] quotient groups - keith conrad
By Theorem 2.11, we can meaningfully multiply cosets of a normal subgroup N of a group G by multiplying representatives for two cosets and passing to the coset ...
[15]
[PDF] Chapter 6, Ideals and quotient rings
Let I be an ideal of a ring R. Congruence modulo I is an equivalence relation. Proof. reflexive: a − a = 0 ∈ I since I is a subring.
[16]
[PDF] Contents 3 Homomorphisms, Ideals, and Quotients - Evan Dummit
Definition: If I is an ideal of the ring R, then we say a is congruent to b modulo I, written a ≡ b (mod I), if a − b ∈ I. ◦ As in Z and F[x], congruence modulo ...<|control11|><|separator|>
[17]
[PDF] Math 121 Homework 4 Solutions
Prove that R[x]/(x2 + 1) is a field which is isomorphic to the field of complex numbers. We will give two solutions. The first solution uses only facts that are ...
[18]
[PDF] Lecture 13: Ideals; kernels of ring homomorphisms - UCSD Math
Lecture 13: Ideals; kernels of ring homomorphisms. Thursday, August 24, 2017 ... Lecture 13: Prime and maximal ideals. Sunday, August 27, 2017. 10:19 PM.
[19]
[PDF] Math 412. Adventure sheet on Normal Subgroups
THEOREM 8.11: A subgroup N of a group G is normal if and only if for all g ∈ G,. gNg-1 ⊆ N. Here, the set gNg-1 := {gng-1 | n ∈ N}. NOTATION: If H ⊆ G is any ...
[20]
[PDF] 26 Homomorphisms, Ideals and Factor Rings - UCI Mathematics
The basic idea is that a subring is an ideal if and only if it is the kernel of some ring homo- morphism.Missing: congruence | Show results with:congruence
[21]
[PDF] A Course in Universal Algebra - Department of Mathematics
We introduce the notion of classifying a variety by properties of (the lattices of) congruences on members of the variety. Also, the center of an algebra is ...
[22]
congruence in nLab
Oct 9, 2025 · The coequalizer of a congruence is called a quotient object. The quotient of an effective congruence is called an effective quotient. ...
[23]
quotient object in nLab
### Summary of Quotient Object from nLab
[24]
[PDF] Abelian Categories - Daniel Murfet
Oct 5, 2006 · Definition 38. A category C is normal if every monomorphism is the kernel of some morphism, and is conormal if every epimorphism is the cokernel ...