Find modular inverse of a number

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

• Why do you think that finding a modular inverse would be possible in this case? It does not exist. – Jyrki Lahtonen Aug 15 '14 at 7:46
• 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. – 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$

So

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

So

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

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

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