# Equivalence classes on Z

So I'm given that R is an equivalence relation on Z, and that adding classes in the natural way is well defined. That is, class(a)+class(b) = class(a + b). I want to show that R can only be equality mod n (for some n) or actual equality. I'm provided a hint to take into account the smallest difference present between elements of the same equivalence class...I'm pretty stumped unfortunately.

I think I want to find such a minimal difference between elements and show that any other difference between elements in that class is a multiple of the minimal. The Euclidean algorithm seems relevant to that approach, but methinks I might be entirely misguided...

-
I think you are on the right track. Keep going! –  Alex Becker Sep 14 '12 at 5:46
And consider class(0)+class(0)=class(0). –  Hagen von Eitzen Sep 14 '12 at 6:06

We denote the equivalence relation by $\equiv$.
By the assumption, $a \equiv a'$ and $b \equiv b'$ imply $a + a' \equiv b + b'$. In particular, $a \equiv a'$ implies $a + b \equiv a' + b$ for every $b \in \mathbb{Z}$. Hence $a \equiv 0$ implies $-a \equiv 0$.
Let $I = \{a \in \mathbb{Z}\colon a \equiv 0\}$. If $I = 0$, then $\equiv$ is clearly equality. So we suppose $I \neq 0$. Let $n$ be the least positive integer belonging to $I$. Let $x \in I$. $x$ can be written as $x = nq + r$, where $q, r \in \mathbb{Z}$ and $0 \le r < n$. Since $nq \in I$, $r = x - nq \in I$. Hence $r = 0$. Hence $I = \mathbb{Z}n$. Therefore the equivalence relation is defined by mod $n$.