Multiplicative inverses and co-primes

I'm working out some examples on multiplicative inverses. I understand how to solve for a multiplicative inverse using the Extended Euler's algorithm, but I don't understand the principles which enable this solution.

In particular, everything notes that for a multiplicative inverse to exist of a number a in multiplicative group modulo n, that a and n must be co-prime (thus, GCD(a,n) = 1).

I can work out plenty of examples where I won't be able to find a multiplicative inverse if they are not co-prime -- but I don't understand why this works.

$ak\equiv 1 \pmod n\,$ means, for some $\,j,\,$ $\,ak+nj = 1,\,$ so $\,d\mid a,n\,\Rightarrow\, d\mid 1,\,$ so $\,\gcd(a,n)=1.$
Conversely, by the ext Euclidean algorithm $\, \gcd(a,n)=1\,\Rightarrow\, ak+nj = 1\,\Rightarrow\,ak\equiv 1\pmod n,\,$ for some $\,j,k.$
• @BSchlinker The proof shows that the only (positive) common divisor of $\,a,n\,$ is $\,d = 1.\,$ Therefore, in particular, their greatest common divisor is $\, 1.\ \$ – Bill Dubuque Apr 23 '14 at 19:16
• @BSchlinker More generally, using essentially the same method, one can show $\ ax\equiv b\pmod n\$ has a solution $\,x\iff \gcd(a,n)\mid b.\,$ Yours is the special case $\,b = 1.\ \$ – Bill Dubuque Apr 23 '14 at 19:23
• @BSchlinker One can also view it is terms of divisibility mod $\,n,\,$ namely, notice that $\ ax\equiv b\pmod n\,$ is solvable $\iff a\mid b\pmod n\iff (a,n)\mid b,\,$ see this answer. – Bill Dubuque Apr 23 '14 at 19:44