Q.Let $n$ be a fixed positive integer. Define a relation $R$ in $\mathbb{Z}$ as follows: $\forall\, a, b \in \mathbb{Z}$, $aRb$ if and only if $a - b$ is divisible by $n$. Show that $R$ is an equivalence relation.

Concept: Equivalence Relation Proof — we check reflexivity, symmetry, and transitivity.

1. Reflexive: For any $a \in \mathbb{Z}$, $a - a = 0$, and $0$ is divisible by $n$. So $aRa$ holds.

2. Symmetric: If $aRb$, then $n \mid (a - b)$. Hence $n \mid -(a - b) = b - a$, so $bRa$ holds. …

The core idea here is that divisibility by a fixed integer $n$ creates a natural way to group integers into classes based on their remainder when divided by $n$. The relation $R$ simply says two integers are related if their difference is a multiple of $n$ — which is exactly the definition of being congruent modulo $n$, written as $a \equiv b \pmod{n}$.

To prove any relation is an equivalence relation, we must check three properties: reflexivity, symmetry, and transitivity. Each one follows directly from basic facts about divisibility.

1. Reflexivity: For any $a \in \mathbb{Z}$, we need $aRa$.

   Since $a - a = 0$, and $0$ is divisible by every positive integer $n$ (because $0 = n \cdot 0$), we have $n \mid (a-a)$. Hence $aRa$ holds for all $a$.

2. Symmetry: If $aRb$, then $n \mid (a-b)$. We need to show $bRa$, i.e., $n \mid (b-a)$.

   If $a-b = nk$ for some integer $k$, then $b-a = -(a-b) = n(-k)$, which is also a multiple of $n$. So $n \mid (b-a)$, and $bRa$ follows.

3. Transitivity: If $aRb$ and $bRc$, then $n \mid (a-b)$ and $n \mid (b-c)$. We need $n \mid (a-c)$.

   Write $a-b = nk$ and $b-c = n\ell$ for integers $k, \ell$. Adding these gives:

Since $k+\ell$ is an integer, $a-c$ is a multiple of $n$. Thus $n \mid (a-c)$, so $aRc$. …

Method: Proving a relation is an equivalence relation

To prove $R$ is an equivalence relation, verify reflexive, symmetric and transitive — in that order — using the defining condition.

Steps

Step 1: Reflexive

Show $(a,a)\in R$ for every $a$. For "$n\mid(a-b)$", note $a-a=0$ and $n\mid 0$, so $aRa$ always holds.

Step 2: Symmetric

Assume $aRb$, i.e. $a-b=nk$. Then $b-a=-nk=n(-k)$ is also a multiple of $n$, so $bRa$.

Step 3: Transitive

Assume $aRb$ and $bRc$, i.e. $a-b=nk$ and $b-c=n\ell$. Add them:

$a-c=(a-b)+(b-c)=n(k+\ell),$ …

Common Mistakes

Mistake 1: Thinking transitivity needs $a-b$ and $b-c$ to be the same multiple of $n$

Why it's wrong: they can be different multiples $nk$ and $n\ell$; their sum $n(k+\ell)$ is still a multiple of $n$. Correct approach: add the two divisibility statements and factor out $n$.

Mistake 2: Forgetting $0$ is divisible by $n$ when proving reflexivity

Why it's wrong: reflexivity relies on $a-a=0$ and $n\mid0$; doubting this leaves the proof incomplete. Correct approach: state $0=n\cdot0$, so $n\mid0$. …