The converse statement of $\gcd(a,n)=1\implies a^{-1}(\mod n)\textrm{ exists},$ given that $a\in\mathbb Z, n\in\mathbb Z^+$?

Question

Is the converse of the following theorem correct?

Let $a\in\mathbb Z, n\in\mathbb Z^+, \gcd(a,n)=1\implies a^{-1}(\mod n)$ exists.

My trying:

Exist $a^{-1}$ such that $aa^{-1}\equiv 1(\mod n)$, which means $n\mid(aa^{-1}-1)$, so $aa^{-1}-nk=1,$ for some $k\in\mathbb Z,$ so $\gcd(a,n)=1.$

Is this correct?

Answer 1

Yes, that is correct, assuming that you can use the fact that, given integers $m$ and $n$, $\gcd(m,n)=1$ if and only if there are integers $\alpha$ and $\beta$ such that $\alpha m+\beta n=1$.

Otherwise, after you have reached the equality $aa^{-1}-nk=1$, you can say that if a natural number $d$ is such that $d\mid a$ and $d\mid n$, then $d\mid aa^{-1}-nk$, which means that $d\mid 1$. Therefore, $d=1$ and so $\gcd(a,n)=1$.