Recently I have read extended euclid's algorithm which is used to find out the modular inverse of a number N whith respect to MOD such that $\gcd(N,MOD)=1.$ But I have a doubt that how to find modular inverse of a number if $\gcd(N,MOD)\neq1$?

  • $\begingroup$ Why do you think that finding a modular inverse would be possible in this case? It does not exist. $\endgroup$ – Jyrki Lahtonen Aug 15 '14 at 7:46
  • $\begingroup$ This is one of those subtle issues that often gets skipped over in texts etc. I always think it should be spelled out BEFORE telling you how to construct the inverse that not every number mod $n$ can have an inverse. $\endgroup$ – fretty Aug 15 '14 at 7:57

You should have doubts because it may not always be possible!

Consider the numbers $6$ and $9$ that have gcd $3$

Curiously $6^2 \equiv 0 \mod 9$


$$ \frac{1}{6^2} \equiv \ UNDEFINED \ \mod 9$$


$$ \frac{1}{6} \equiv \ UNDEFINED \ \mod 9$$

And there is an example of a pair of $N$ and $MOD$ with no modular inverse

  • 4
    $\begingroup$ It will never be possible: $x$ has a multiplicative inverse modulo $n$ if and only if $x$ and $n$ are coprime. $\endgroup$ – Warren Moore Aug 15 '14 at 7:45
  • $\begingroup$ was hoping OP could derive that independently but I suppose this comment^ will make this post more useful to others in the future :) $\endgroup$ – frogeyedpeas Aug 15 '14 at 7:48

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.