Given a number $n$ and modulus $m$, the modular inverse is the number $x$ such that $$ xa \equiv 1 \mod m.$$

If I have only the number $a$, is it possible to find all the numbers $m$, for which $a$ has a multiplicative inverse?

And if it's possible, this algorithm how is computationally complex?

  • 1
    $\begingroup$ This happens exactly for all numbers comprime with $a$. So, for example you can pick $m=a+1$, having a computaional complexity of $O(1)$. $\endgroup$ – Crostul Mar 31 '17 at 9:55
  • $\begingroup$ You seem to use $a$ and $n$ for the same thing. Is that right? $\endgroup$ – Arthur Mar 31 '17 at 9:55
  • $\begingroup$ Yeah, thank to pointing me, I've just corrected the question $\endgroup$ – user2548436 Mar 31 '17 at 9:56
  • $\begingroup$ Given $a$, if you pick an $m$ that shares no factors with it, then there exist integers $x$ and $y$ for which $ax + my = 1$; modulo $m$, this means that $ax = 1$ i.e. that $x$ serves as the modular inverse for $a$. This follows from Bézout's identity and the (non-unique) $x$ and $y$ can be found using the extended GCD algorithm. $\endgroup$ – Benjamin Dickman Mar 31 '17 at 10:00
  • $\begingroup$ My question is how to find all the m for wich a have the multiplicative inverse $\endgroup$ – user2548436 Mar 31 '17 at 10:04

Here's an answer summarizing the comments and addressing the computational complexity.

You can't find "all the numbers $m$" since there are infinitely many, so suppose you are interested in those less than some $M$. You need to look at all the integers less than $M$, which bounds your time as $\Omega(M)$.

You can compute the greatest common divisor of $a$ and $m$ in time $O(\log (a)$. Since $a$ is fixed that's essentially a constant in your analysis, so the time is $O(M)$.

In an actual application there may be ways to bypass computing all those greatest common divisors and speed things up. You could factor $a$, then use an Eratosthenes sieve to cross off all the integers less than $M$ that share a prime divisor of $a$.


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.