Modular Inverse Algorithm Tutorial

Modular Multiplicative Inverse

The modular inverse of $a$ modulo $m$ is a number $x$ such that $a \cdot x \equiv 1 \pmod{m}$. It's also known as the multiplicative inverse in modular arithmetic.

You can only find the modular inverse when $\gcd(a, m) = 1$. When $m$ is prime, you use Fermat's Little Theorem: $a^{-1} \equiv a^{m-2} \pmod{m}$.

function modInverse(a, m):
    return power(a, m - 2, m)

function power(x, n, mod):
    result = 1
    x = x mod mod
    while n > 0:
        if n is odd:
            result = (result * x) mod mod
        x = (x * x) mod mod
        n = n / 2
    return result

When to use it: When you divide in modular arithmetic, you multiply by the inverse instead. For $(a / b) \mod m$, you compute $(a \cdot b^{-1}) \mod m$.

Extended GCD method: For non-prime moduli, you use the extended Euclidean algorithm which finds $x$ and $y$ such that $ax + my = \gcd(a, m)$.

Applications: You use modular inverse for division in modular arithmetic, computing nCr mod p, RSA encryption, and Chinese Remainder Theorem.

Time complexity: $O(\log m)$ for the binary exponentiation.

Space complexity: $O(1)$ for iterative version.