# Multiplicative inverses in modular arithmetic

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?

• 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)$. – Crostul Mar 31 '17 at 9:55
• You seem to use $a$ and $n$ for the same thing. Is that right? – Arthur Mar 31 '17 at 9:55
• Yeah, thank to pointing me, I've just corrected the question – user2548436 Mar 31 '17 at 9:56
• 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. – Benjamin Dickman Mar 31 '17 at 10:00
• My question is how to find all the m for wich a have the multiplicative inverse – user2548436 Mar 31 '17 at 10:04

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