0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – BSchlinker Apr 23 '14 at 18:58
  • $\begingroup$ @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.\ \ $ $\endgroup$ – Bill Dubuque Apr 23 '14 at 19:16
  • 1
    $\begingroup$ @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.\ \ $ $\endgroup$ – Bill Dubuque Apr 23 '14 at 19:23
  • 1
    $\begingroup$ @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. $\endgroup$ – Bill Dubuque Apr 23 '14 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.