## Characterization of zero divisors and units in ZZ/(n)

Let $n \in \mathbb{Z}$, $n > 1$, and let $a \in \mathbb{Z}$ with $1 \leq a \leq n$. Prove that if $a$ and $n$ are not relatively prime, then there exists an integer $b$ with $1 \leq b < n$ such that $ab = 0 \mod n$. Deduce that there cannot exist an integer $c$ such that $ac = 1 \mod n$.

Suppose $\mathsf{gcd}(a,n) = d \neq 1$. Then we have $db = n$ for some $b$, and $1 \leq b < n$. Moreover $a = md$ for some $m$, so that, mod n, we have $ab = mdb = mn = 0$.

Suppose now that $ac = 1$ mod n for some $c$. Then we have, mod n, $0 = 0 \cdot c = a \cdot b \cdot c = a \cdot c \cdot b = 1 \cdot b = b$. But then $b = 0$, a contradiction. So no such $c$ exists.