Algebra Solutions: 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.

Algebra Solutions

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

No comments:

Post a Comment