1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Why do you think that finding a modular inverse would be possible in this case? It does not exist. $\endgroup$ Aug 15, 2014 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, 2014 at 7:57

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • 4
    $\begingroup$ It will never be possible: $x$ has a multiplicative inverse modulo $n$ if and only if $x$ and $n$ are coprime. $\endgroup$ Aug 15, 2014 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$ Aug 15, 2014 at 7:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .