Prove that for a fixed n, =n is an equivalence relation on N. (It is actually an
ID: 2966185 • Letter: P
Question
Prove that for a fixed n, =n is an equivalence relation on N. (It is actually an equivalence relation on Z as well, you can prove either.) A relation R on S is said to be reflexive if (s, s) R for each s S. A relation 7Z on S is said to be symmetric if (s, t) R implies (t, s) R. A relation 1Z on S is said to be transitive if (s, t) R and (t, r) R implies (s, r) R. A relation R on S is said to be an equivalence relation on S if it is reflexive, transitive and symmetric. For a fixed natural number n, define the relation =n on Z by r =n q if and only if there is an integer k for which nk = r - q. (That is, tl divides r - q.) When read the expression r =n q as "r is congruent to q modulo n."Explanation / Answer
Reflexivity is trivial, we need to show there is some k for which nk = s - s, but since s - s = 0, k = 0 will always work regardless of n.
Symmetry is also trivial, given a k1 such that nk1 = s - t we must show there is also some k2 such that nk2 = t - s. Let k2 = -k1 and it is proven.
Transitivity is more interesting, we are given k1 such that nk1 = s - t and we are given k2 such that nk2 = t - r. We need to find k3 such that nk3 = s - r. If we add the two equations, we get nk1 + nk2 = s - t + t - r which simplifies to n(k1 + k2) = s - r. Therefore let k3 = k1 + k2 and we have proven transitivity.
Since we have reflexivity, symmetry, and transitivity, congruence modulo N is an equivalence relation.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.