Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

On a practice exam, our teacher gave us this answer as the third point in proving:

Let $n$ be a positive integer and let $P = \{$equivalence classes for is-congruent-to-mod-$n\}$. Show that $P$ is a partition of the set of integers.

$\bigcup_{a\in\mathbb{Z}_n} [a] = \mathbb{Z}$: Clearly $\bigcup_{a\in\mathbb{Z}_n} [a] \subseteq \mathbb{Z}$ as each element in each set is an integer. Now let $z \in\mathbb{Z}$. By the division algorithm there is a unique pair $(q,r)$ with $0 \leq r < n$ such that $z=qn+r$. Thus $z\equiv r\pmod{n}$. That is $z\in[r]$, so $z\in\bigcup_{a\in\mathbb{Z}_n}[a]$.

My question is, I do not understand what this is saying. I do not understand the notation, nor do I understand what this is proving.

share|cite|improve this question
Do you know what a partition is? – Holdsworth88 May 14 '12 at 16:39
Yes. I know that each subset in a partition is not empty, and that all of the subsets together form the original set, and that the subsets are disjoint – Ali May 14 '12 at 16:51
for non-emptiness show that for each number in $\{0,\dots,n-1\}$ there is an integer number congruent to it. – Keivan May 14 '12 at 17:12
for the second part show that each integer is congruent to some number in $\{0,\dots,n-1\}$. (somehow converse of the above!) – Keivan May 14 '12 at 17:14
And finally for the most important part, show that if $a,b$ are two different integers, they are either congruent mod $n$ or not! – Keivan May 14 '12 at 17:16

We have this little theorem that can be pretty helpful in this situations:

Theorem: Let $\,X\,$ be a non-empty set, and let $\,S:=\{A_i\;\;;\;\;i\in I\}\,$ be a collection of non-empty subsets of $\,X\,$ . Then $\,S\,$ is a partition of $\,X\,$ iff the sets in $\,S\,$ are the equivalence classes of some equivalence relation on $\,X\,$.

Proof: This is a rather easy but interesting exercise.

Well, now just prove that $\,P\,$ fulfills the requirements of the above theorem, for example: define a relation $\,R_n\,$ on $\,\mathbb Z\,$ by $$aR_nb\,\Longleftrightarrow a=b+kn\,\,,\,\text{for some integer}\,\,k$$ It is pretty straightforward to check reflexivity, symmetry and transitivity, and the equivalence classes are the modulo n ones.

share|cite|improve this answer
And that theorem that says that if $xRa$ and $xRb$ then $\hat a =\hat b$ (i.e. two equivalence classes are either equal or disjoint) – Pedro Tamaroff Jun 23 '12 at 3:32
That is part of the above theorem and of the definition [1] of partition, as far as I am aware.[1] – DonAntonio Jun 23 '12 at 8:19

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.