an invertible element $i$ in $\mathbb Z_n$ must be coprime to $n$ Let $n$ be an integer and $i\in \{1,\cdots,n-1\}$. I want to show that $i$ is invertible in $\mathbb Z_n$ if and only if $i$ is coprime to $n$.
One way is easy. suppose $i$ is coprime to $n$ then $\alpha i +\beta n=1$ for some  $\alpha,\beta \in \mathbb Z$, so $\alpha i =1 - \beta n$ hence $\alpha i \equiv 1 (mod\; n)$ and 
$i$ is invertible.
the other way is less obvious to me. suppose that $i$ is invertible in $\mathbb Z_n$. Why it must be coprime to $n$? my guess: suppose they are not coprime then $i=da$ and $n=db$ for some $d>1,a,b$ but since $i$ is invertible then $li=1+mn$ for some $l,m$ hence $lda=1+mdb$ so 
$d(la-mb)=1$ this implies that $d=\pm 1$ which is impossible since $d>1$
is this correct and is there more conceptual argument for this?
 A: My intuition is along the lines of your second argument: if $i=da$ and $n=db$, all integer multiples of $i$ must be multiples of $d$ and hence can never be one plus a mutiple of $d$.
A: Your argument works perfectly well. A variant with a more abstract flavour that uses your notation is to observe that 
$$ib=(ad)b=a(db)=an$$
so $ib \equiv 0 \pmod{n}$.
If $j$ were an inverse of $i$, then we would have 
$$j(ib)\equiv j\cdot 0\equiv 0\pmod{n}.$$
But
$$j(ib)=(ji)b\equiv b\pmod{n}.$$
Thus $b\equiv 0 \pmod{n}$, which is impossible if $d>1$, since then $0<b<n$.
A: Suppose that $\overline{a}$ is invertible in $Z_n$. Then there is some $\overline{b}$ in $Z_n$ such that
$$\overline{a}\overline{b} = \overline{1}$$
It follows that $n$ divides $ab$ with remainder $1$, in other words:
$$ab = qn + 1$$
Assume by contradiction that $a$ and $n$ are not coprimes, that is, $\gcd(a, n) = d > 1$. Dividing the above equation by $d$ we have:
$$\frac{ab}{d} = \frac{qn}{d} + \frac{1}{d}$$
Note that the left side of the equation is an integer and the right side is a rational, which is absurd.
