congruence relation

Show Summary Details

Quick Reference

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 ab (modulo m) One of the most important uses of the congruence relation in computing is in generating random integers. A sequence s0,s1,s2,… of integers between 0 and (m - 1) inclusive can be generated by the relation sn+1asn + c (modulo m) The values of a, c, and m must be suitably chosen.

ab (modulo m)


sn+1asn + c (modulo m)

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.

x R u and y R v

then (x ° y) R (u ° v)

Subjects: Computing.

Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.