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 s0,s1,s2,… of integers between 0 and (m - 1) inclusive can be generated by the relation sn+1 ≡ asn + c (modulo m) The values of a, c, and m must be suitably chosen.
a ≡ b (modulo m)
sn+1 ≡ asn + 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)
Users without a subscription are not able to see the full content. Please,
or login to access all content.