congruence relation

views updated

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 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.

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 (xy) R (uv)

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.