Question

Let $n$ be a fixed positive integer. A relation $R$ is defined in the set of integers $\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 relation is known as "congruence modulo $n$", written as $x \equiv y \pmod n$. It forms the foundational basis of modular arithmetic in number theory.

Answer 1

Concept: For a relation $R$ on a set to qualify as an equivalence relation, it must simultaneously satisfy three independent logical properties: reflexivity, symmetry, and transitivity.
• Reflexivity: For all $x \in \mathbb{Z}$, $(x, x) \in R$.
• Symmetry: If $(x, y) \in R$, then it must follow that $(y, x) \in R$.
• Transitivity: If $(x, y) \in R$ and $(y, z) \in R$, then it must follow that $(x, z) \in R$.

Step 1: Verify the Reflexive and Symmetric properties of the relation.
* Property 1: Reflexivity Let $x$ be an arbitrary integer belonging to $\mathbb{Z}$. Consider the difference of $x$ with itself: \[ x - x = 0 \] Since zero is perfectly divisible by any positive integer $n$ (as $0 = 0 \cdot n$), the condition is satisfied. Therefore, $(x, x) \in R$ for all $x \in \mathbb{Z}$. This proves that $R$ is reflexive. * Property 2: Symmetry Let $x, y \in \mathbb{Z}$ and assume that $(x, y) \in R$. By definition, this means $(x - y)$ is divisible by $n$: \[ x - y = k \cdot n \quad \text{for some integer } k \in \mathbb{Z} \] Let us multiply both sides of this equation by $-1$: \[ -(x - y) = -k \cdot n \quad \implies \quad y - x = (-k) \cdot n \] Since $k$ is an integer, $-k$ is also an integer. This shows that $(y - x)$ is also divisible by $n$. Therefore, $(y, x) \in R$, which proves that $R$ is symmetric.

Step 2: Verify the Transitive property of the relation and draw the final conclusion.
* Property 3: Transitivity Let $x, y, z \in \mathbb{Z}$ and assume that both $(x, y) \in R$ and $(y, z) \in R$. This implies: \[ x - y = k_1 \cdot n \quad \text{for some integer } k_1 \in \mathbb{Z} \] \[ y - z = k_2 \cdot n \quad \text{for some integer } k_2 \in \mathbb{Z} \] Let us add these two equations together: \[ (x - y) + (y - z) = k_1 \cdot n + k_2 \cdot n \] Simplifying the left side by canceling out $y$: \[ x - z = (k_1 + k_2) \cdot n \] Since the sum of two integers $(k_1 + k_2)$ is also an integer, this shows that $(x - z)$ is divisible by $n$. Therefore, $(x, z) \in R$, which proves that $R$ is transitive. Since the relation $R$ is reflexive, symmetric, and transitive, it is proven to be an equivalence relation.