Congruence relation

related topics
{math, number, function}
{math, energy, light}

In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group, ring, or vector space) that is compatible with the structure. Every congruence relation has a corresponding quotient structure, whose elements are the equivalence classes (or congruence classes) for the relation.

Contents

Basic example

The prototypical example of a congruence relation is congruence modulo n on the set of integers. For a given positive integer n, two integers a and b are called congruent modulo n, written

if ab is divisible by n (or equivalently if a and b have the same remainder when divided by n).

for example, 37 and 57 are congruent modulo 10,

since 57 − 37 = 20 is a multiple of 10, or equivalently since both 37 and 57 have a remainder of 7 when divided by 10.

Congruence modulo n (for a fixed n) is compatible with both addition and multiplication on the integers. That is, if

then

The corresponding addition and multiplication of equivalence classes is known as modular arithmetic. From the point of view of abstract algebra, congruence modulo n is a congruence relation on the ring of integers, and arithmetic modulo n occurs on the corresponding quotient ring.

Definition

The definition of a congruence depends on the type of algebraic structure under consideration. Particular definitions of congruence can be made for groups, rings, vector spaces, modules, semigroups, lattices, and so forth. The common theme is that a congruence is an equivalence relation on an algebraic object that is compatible with the algebraic structure, in the sense that the operations are well-defined on the equivalence classes.

Full article ▸

related documents
Toeplitz matrix
CYK algorithm
Deque
Compiler-compiler
Normal subgroup
Quaternion group
Hidden Markov model
List of logarithmic identities
Interior (topology)
Identity element
Bézout's theorem
Box-Muller transform
Sigma-algebra
Inverse element
Homeomorphism
Parity (mathematics)
De Moivre's formula
Event (probability theory)
Combination
Coset
Euphoria (programming language)
Nash embedding theorem
PSPACE-complete
Uncountable set
Infinite product
Chomsky normal form
Convex hull
Memento pattern
Linear congruential generator
Harmonic series (mathematics)