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.
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 a − b 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
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.
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 ▸