# 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.$
• I can follow everything in your first statement, until you make the claim that because d|a,n and d|1 that the gcd(a,n) = 1. I see that if d|1, then d must be 1. But I don't understand how you can jump to knowing the GCD of the two things must be 1 from this. (I'm guessing it is because there is no other combination of k,j for which this equation will equal 1, and for which d will divide a,n and also divide ak + nk (1). – BSchlinker Apr 23 '14 at 18:58
• @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