Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 3 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.