Does this proof work? Is there a simpler one (precluding citing other theorems)?
Suppose $ax \equiv 1 \bmod{n}$. Then $ax = kn + 1$. We have some $d = \gcd(a, n)$ such that $a = da'$, $n = dn'$, and $d > 1$. So $da'x = kdn' + 1 \implies d(a'x - n'k) = 1 \implies a'x - n'k = 1 \mathbin/ d$. The LHS is an interger, but for $d > 1$, the RHS isn't. So the equality cannot hold.
You can consider this one: Let $ax \equiv 1$ mod $n$ Suppose $(a,n) = d$ So if $ ax \equiv 1$ mod $n$ $\rightarrow ax = kn + 1, k \in \mathbb{Z}$
Now we only want to consider: $ax + (-n)k = 1$ and this is a diofantine linear equation, so this equation has a solution if and only if $(a,-n) \lvert 1$, now it's clear that $(a,-n) = (a,n) = d $. Therefore $ d \lvert 1$ so $ (a,n) = d = 1$.