# Invertible Elements of $\mathbb{Z}_{n}$

I have the following problem that I am stuck on.

Assume $n>1$ and let $U(\mathbb{Z}_{n})$ be the set of invertible elements of $\mathbb{Z}_{n}$ as a quotient ring. Show that $U(\mathbb{Z}_{n})$ consists of those elements $\overline{x}=x+n\mathbb{Z}$ for which $gcd(x,n)=1$.

My work so far: Let $\overline{x}\in U(\mathbb{Z}_{n})$. Then $\exists$ $\overline{y}\in\mathbb{Z}_{n}$ such that $\overline{x} \cdot\overline{y}=\overline{xy}=\overline{1}$. Thus, we have $xy-1=kn$ in $n\mathbb{Z}$ for some $k\in\mathbb{Z}$.......

I'm not sure how to go from here. Am I even on the right track? Thanks in advance for any help!

• You're definitely on the right track. Rearranging, you have $xy - kn = 1$. Suppose $d$ divides both $x$ and $n$; what can you conclude from the above equation? – André 3000 Apr 26 '17 at 3:47
• If $d$ is a common divisor to $x$ and $n$, then can we assume that $d$ divides $xy$ and $kn$? – Sir_Math_Cat Apr 26 '17 at 3:49
• Well, sure, but that's a weaker statement than saying $d$ divides $x$ and $n$. What happens if you substitute $x = da$ and $n = db$ into the equation? – André 3000 Apr 26 '17 at 3:51
• $d$ divides $(ay-kb)$? Sorry; I'm not quite following where this should be going. – Sir_Math_Cat Apr 26 '17 at 3:53
• Okay, thanks for the help! It makes way more sense now! – Sir_Math_Cat Apr 26 '17 at 4:02

It states that there always exists $(a,b)\in\mathbb Z^2$ such that $ax+bn=\gcd(x,n)$. In addition, $\gcd(x,n)$ is also the smallest positive number achievable by linear combination of $x$ and $n$ (for $a,b$ not both zero of course).
Once you get this, $x$ invertible leads to $\exists a\in\mathbb Z\mid ax\equiv 1\pmod{n}\iff \exists k\in\mathbb Z\mid ax=1+kn$ and finally there exists $(a,k)\in\mathbb Z^2$ such that $ax+(-k)n=1\iff \gcd(x,n)=1$.