# congruence relation

**congruence relation** **1.** An equivalence relation defined on the integers in the following manner. Let *m* be some given but fixed positive integer and let *a* and *b* be arbitrary integers. Then *a* is congruent to *b* modulo *m* if and only if (*a *– *b*) is divisible by *m*. It is customary to write this as *a* ≡ *b* (modulo *m*)

One of the most important uses of the congruence relation in computing is in generating random integers. A sequence *s*_{0},*s*_{1},*s*_{2},…

of integers between 0 and (*m *– 1) inclusive can be generated by the relation *s _{n}*

_{+1}≡

*as*+

_{n}*c*(modulo

*m*)

The values of

*a*,

*c*, and

*m*must be suitably chosen.

**2.**An equivalence relation

*R*(defined on a set

*S*on which a dyadic operation ◦ is defined) with the property that whenever

*x R u*and

*y R v*then (

*x*◦

*y*)

*R*(

*u*◦

*v*)

This is often referred to as the

*substitution property*. Congruence relations can be defined for such algebraic structures as certain kinds of algebras, automata, groups, monoids, and for the integers; the latter is the congruence modulo

*m*of def. 1.

#### More From encyclopedia.com

#### You Might Also Like

#### NEARBY TERMS

**congruence relation**