Question

Let \(n\) be a fixed positive integer. A relation \(R\) is defined in set \(\mathbb{Z}\) such that \(R = \{(x, y) : (x - y) \text{ is divisible by n, x, y \in \mathbb{Z}\}\). Determine if \(R\) is an equivalence relation.}

Hint:

This specific relation is known as "congruence modulo n".
Divisibility properties of integers (like 0 being divisible by everything) are key to proving equivalence relations on \(\mathbb{Z}\).

Answer 1

Concept:
• A relation is an equivalence relation if it is reflexive, symmetric, and transitive.
• Reflexive: \(aRa\) for all \(a\).
• Symmetric: \(aRb \implies bRa\).
• Transitive: \(aRb\) and \(bRc \implies aRc\).

Step 1: Check for Reflexivity
For any \(x \in \mathbb{Z}\), we have \(x - x = 0\).
Since 0 is divisible by any positive integer \(n\), \(x - x\) is divisible by \(n\).
Thus, \((x, x) \in R\) for all \(x \in \mathbb{Z}\). \(R\) is reflexive.

Step 2: Check for Symmetry
Let \((x, y) \in R\). Then \((x - y)\) is divisible by \(n\).
So, \(x - y = kn\) for some integer \(k\).
Then, \(y - x = -(x - y) = -kn = (-k)n\).
Since \(-k\) is also an integer, \((y - x)\) is divisible by \(n\).
Thus, \((y, x) \in R\). \(R\) is symmetric.

Step 3: Check for Transitivity
Let \((x, y) \in R\) and \((y, z) \in R\).
Then \((x - y) = k_1n\) and \((y - z) = k_2n\) for some integers \(k_1, k_2\).
Adding these two equations:
\[ (x - y) + (y - z) = k_1n + k_2n \] \[ x - z = (k_1 + k_2)n \] Since \((k_1 + k_2)\) is an integer, \((x - z)\) is divisible by \(n\).
Thus, \((x, z) \in R\). \(R\) is transitive.

Step 4: Conclusion
Since the relation is reflexive, symmetric, and transitive, \(R\) is an equivalence relation.