Prove that $[a]_n$ is a unit in $\mathbb{Z}_n$ (i.e. $[a]_n$ has a multiplicative inverse) if and only if $\gcd(a, n) = 1$.

Question

Let $n \in \mathbb{Z}$ with $n\geq2$, and let $a\in \mathbb{Z}$.

Prove that $[a]_n$ is a unit in $\mathbb{Z}_n$ (i.e. $[a]_n$ has a multiplicative inverse) if and only if $\gcd(a, n) = 1$.

I know for $[a]_n$ to be a unit, there needs to exist an element $[b]_n$ such that $[a]_n[b]_n$=1. I then know we must end up with $ax+ny=1$ for some integers $x$ and $y$. I am not sure how to get here though.

What I have tried: I have tried $[a]_n[b]_n$=1 and from this, going to $(a=qn+x)(b=kn+y)=1$, but I do not think I can go anywhere from this.

Can anyone help, please?

Answer 1

If

$\gcd(a, n) = 1, \tag 1$

then in accord with Bezout's identity there exist

$b, c \in \Bbb Z \tag 2$

such that

$ab + nc = 1; \tag 3$

thus

$ab + nc \equiv 1 \mod n; \tag 4$

that is,

$[a]_n[b]_n + [n]_n [c]_n = [1]_n \tag 5$

in $\Bbb Z_n$; but

$[n]_n = 0, \tag 6$

whence (5) reduces to

$[a]_n[b]_n = [1]_n; \tag 7$

i.e., $[a]_n$ is a unit in $\Bbb Z_n$ with inverse $[b]_n$.

Now if (7) binds for some $b \in \Bbb Z$ (given of course $a \in \Bbb Z$), then writing out $[a]_n$ etc. in conventional coset form we find

$(a + n\Bbb Z)(b + n\Bbb Z) = 1 + n\Bbb Z, \tag 8$

or

$ab + n\Bbb Z = 1 + n\Bbb Z, \tag 9$

that is

$ab - 1 = 0 + n\Bbb Z = n\Bbb Z, \tag{10}$

whence

$ab - 1 \in n\Bbb Z \tag{11}$

or

$ab = 1 = nz, \; z \in \Bbb Z; \tag{12}$

finally, this yields

$an + nz = 1, \tag{13}$

or

$\gcd(a, n) = 1, \tag{14}$

as was to be shown.