Exercise 0.3.2 ($|\mathbb{Z}/n\mathbb{Z}| = n$)

Question

Prove that the distinct equivalence classes in $\mathbb{Z}/n\mathbb{Z}$ are precisely $\overline{0}, \overline{1}, \overline{2}, \ldots, \overline{n-1}$ (use the Division Algortihm).

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

\begin{proof} 
Consider the map 
$$f\ 
\left\{
\begin{array}{ccl}
[\![0, n[\![ & 	o & \Z/n\Z\
k & \mapsto & \overline{k}.
\end{array}
ight.
$$
Then 
\begin{itemize}
\item $f$ is surjective: Let $\overline{k}$ be any class of $\Z/n\Z$, where $k \in \Z$. The Euclidean division gives $q,r$ such that
$$k = q n + r,\qquad 0 \leq r < n.$$
Then $k \equiv r \pmod n$, so $\overline{k} = \overline{r} = f(r)$, since $r \in [\![0, n[\![ $. So $f$ is surjective.

\item $f$ is injective: If $\varphi(i) = \varphi(j)$, where $i, j \in [\![0, n[\![ $, then $\overline{i} = \overline{j}$, so
$$ i \equiv j \pmod n,\qquad 0 \leq i <n, \ 0 \leq j <n.$$
Therefore $n$ divides $ j-i$, thus $n$ divides $|j-i| = \pm (j-i)$. But $-n < -i \leq j-i \leq j <n$, thus $|j-i| < n$. If $|j-i| 
e 0$,  then $n \leq |j-i|$ (since $n$ divides $|j-i|$). This is false, so $j - i = 0$. This shows that $f$ is injective.
\end{itemize}
So $f$ is bijective. In other words, the elements of $\Z/n\Z$ are precisely $\overline{0}, \overline{1}, \overline{2}, \ldots, \overline{n-1}$, and these elements are distinct.

$$\Z/n\Z = \{\overline{0}, \overline{1}, \overline{2}, \ldots, \overline{n-1}\},\qquad |\Z/n\Z | = n.$$
\end{proof}

Exercise 0.3.2 ($|\mathbb{Z}/n\mathbb{Z}| = n$)

Answers

Comments

Exercise 0.3.2 ($|\mathbb{Z}/n\mathbb{Z}| = n$)

Answers

Comments

Add answer