Theorem 19.3

Return to Theorems, Glossary, Homework Problems.

Statement:

In the ring $\mathbb{Z}_n$, the divisor of 0 are precisely those nonzero elements that are not relatively prime to n.

Proof:

Let $m \in \mathbb{Z}_n$, where $m\neq 0$, and let the gcd of $m$ and $n$ be $d \neq 1$. Then

(1)
\begin{align} m\left(\frac{n}{d}\right) = \left(\frac{m}{d}\right) n \end{align}

and $\left(\frac{m}{d}\right) n$ gives 0 as a multiple of $n$. Thus $m\left(\frac{n}{d}\right)=0$ in $\mathbb{Z}_n$, while neither $m$ nor $\frac{n}{d}$ is 0, so $m$ is a divisor of 0.

On the other hand, suppose $m\in \mathbb{Z}_n$ is relatively prime to $n$. If for $s\in\mathbb{Z}_n$ we have $ms=0$, then $n$ divides the product $ms$ of $m$ and $s$ as elements in the ring $\mathbb{Z}$. Since $n$ is relatively prime to $m$ and since $n$ divides $ms$, then $n$ must divides $s$ (Property 1 on page 62). So $s=0$ in $\mathbb{Z}_n$.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License