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!

  • $\begingroup$ 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? $\endgroup$ – André 3000 Apr 26 '17 at 3:47
  • $\begingroup$ If $d$ is a common divisor to $x$ and $n$, then can we assume that $d$ divides $xy$ and $kn$? $\endgroup$ – Sir_Math_Cat Apr 26 '17 at 3:49
  • $\begingroup$ 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? $\endgroup$ – André 3000 Apr 26 '17 at 3:51
  • $\begingroup$ $d$ divides $(ay-kb)$? Sorry; I'm not quite following where this should be going. $\endgroup$ – Sir_Math_Cat Apr 26 '17 at 3:53
  • 1
    $\begingroup$ Okay, thanks for the help! It makes way more sense now! $\endgroup$ – Sir_Math_Cat Apr 26 '17 at 4:02

You have it right, you just miss the main asset to solve this problem which is the Bezout identity.

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).

Here is a thread, I participated to recently, but there may be others, Bezout is a popular tool: Understanding the Existence and Uniqueness of the GCD

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.