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...

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 \
eq 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$.