Modular Inverse - Algorithm Tutorial | Repovive

##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######

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

text

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.

Modular Inverse Algorithm Tutorial

Learn

Modular Multiplicative Inverse

Implement this Algorithm

Related Algorithms