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.

Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: