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