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