Find modular inverse of a number

Question

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

Answer 1

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