# proving that $P$ is a partition

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.

-
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

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