Modular Multiplicative Inverse

This article introduces multiplicative inverses modulo an integer and discusses common methods for finding them.

Basic concepts

The multiplicative inverse of a nonzero real number $a\in\mathbf R$ is its reciprocal $a^{-1}$. Similarly, in number theory, the inverse of an integer $a$ modulo $m$ can be defined as $a^{-1}\bmod m$, or simply $a^{-1}$. This is the modular multiplicative inverse, also called the number-theoretic reciprocal.

This is equivalent to saying that $b$ is a solution of the linear congruence $ax\equiv 1\pmod m$. By the properties of linear congruences, the inverse $a^{-1}\bmod m$ exists if and only if $\gcd(a,m)=1$, that is, if $a,m$ are coprime; it is also unique modulo $m$.

Finding a single inverse

The inverse of a single integer can be found in $O(\log m)$ time using the extended Euclidean algorithm or binary exponentiation.

Extended Euclidean algorithm

Finding an inverse is equivalent to solving a linear congruence. Therefore, the extended Euclidean algorithm can find the inverse in $O(\log\min\{a,m\})$ time. Since the corresponding linear equation is special, the relevant steps can be simplified appropriately.

// Extended Euclidean algorithm.
void ex_gcd(int a, int b, int& x, int& y) {
  if (!b) {
    x = 1;
    y = 0;
  } else {
    ex_gcd(b, a % b, y, x);
    y -= a / b * x;
  }
}

// Returns the modular inverse of a modulo m.
// Assumes that gcd(a, m) = 1, so the inverse exists.
int inverse(int a, int m) {
  int x, y;
  ex_gcd(a, m, x, y);
  return (x % m + m) % m;
}

# Extended Euclidean algorithm.
def ex_gcd(a, b):
    if b == 0:
        return 1, 0
    else:
        x1, y1 = ex_gcd(b, a % b)
        x = y1
        y = x1 - (a // b) * y1
        return x, y


# Returns the modular inverse of a modulo m.
# Assumes that gcd(a, m) = 1, so the inverse exists.
def inverse(a, m):
    x, y = ex_gcd(a, m)
    return (x % m + m) % m

This algorithm applies whenever the inverse exists.

Binary exponentiation

This method mainly applies when the modulus is a prime $p$. By Fermat's little theorem, for every $a\perp p$,

By the uniqueness of the inverse, $a^{-1}\bmod p$ equals $a^{p-2}\bmod p$. Therefore, binary exponentiation can calculate it in $O(\log p)$ time:

// Binary exponentiation.
int pow(int a, int b, int m) {
  long long res = 1, po = a;
  for (; b; b >>= 1) {
    if (b & 1) res = res * po % m;
    po = po * po % m;
  }
  return res;
}

// Returns the modular inverse of a prime modulo p.
int inverse(int a, int p) { return pow(a, p - 2, p); }

# Returns the modular inverse of a prime modulo p.
# Use built-in pow function.
def inverse(a, p):
    return pow(a, p - 2, p)

In theory, this method can be extended to a general modulus $m$ using Euler's theorem, calculating the inverse with $a^{\varphi(m)-1}\bmod m$. However, finding the Euler totient function $\varphi(m)$ for a single value is not easy, so this algorithm is inefficient in general.

Finding multiple inverses

In some situations, the inverses modulo $m$ of many integers $a_1,a_2,\cdots,a_n$ must be computed quickly. Solving them one by one takes $O(n\log m)$ time in total. In fact, processing them together allows all inverses to be found in $O(n+\log m)$ time.

Consider the prefix products of the sequence $\{a_i\}$:

As long as every $a_i$ is coprime to $m$, their product $S_n$ is also coprime to $m$. Therefore, the algorithm described above can find $S_n^{-1}\bmod m$. Since the inverse of a product is the product of the inverses, traversing the sequence backwards from $S_n^{-1}$ gives the inverse of every $S_i$:

The inverse of an individual $a_i$ can then be calculated by

A reference implementation follows:

// Returns the modular inverses for each x in a modulo m.
// Assume x mod m exists for each x in a.
std::vector<int> batch_inverse(const std::vector<int>& a, int m) {
  int n = a.size();
  std::vector<int> prod(n);
  long long s = 1;
  for (int i = 0; i < n; ++i) {
    // prod[i] = product of a[0...i-1]; prod[0] = 1.
    prod[i] = s;
    s = s * a[i] % m;
  }
  // s = product of all elements in a.
  s = inverse(s, m);
  std::vector<int> res(n);
  for (int i = n - 1; i >= 0; --i) {
    res[i] = s * prod[i] % m;
    s = s * a[i] % m;
  }
  return res;
}

# Returns the modular inverses for each x in a modulo m.
# Assume x mod m exists for each x in a.
def batch_inverse(a, m):
    n = len(a)
    prod = [0] * n
    s = 1
    for i in range(n):
        # prod[i] = product of a[0...i-1]; prod[0] = 1.
        prod[i] = s
        s = s * a[i] % m
    # s = product of all elements in a.
    s = inverse(s, m)
    res = [0] * n
    for i in reversed(range(n)):
        res[i] = s * prod[i] % m
        s = s * a[i] % m
    return res

The algorithm computes only one inverse of an individual element, so its total time complexity is $O(n+\log m)$.

Linear-time preprocessing of inverses

If the inverses modulo a prime $p$ of the first $n$ positive integers are needed, the recurrence discussed in this section can calculate them in $O(n)$ time. This method is often used to preprocess the reciprocals of the first $n$ positive integers' factorials when calculating binomial coefficients.

For a positive integer $i$ with $1< i < p$, consider Euclidean division:

Taking this equation modulo the prime $p$ gives

Multiplying both sides by $i^{-1}(p\bmod i)^{-1}$ gives

This is the formula for computing inverses by a linear-time recurrence. Since $p\bmod i < i$, it reduces the problem of finding $i^{-1}\bmod p$ to the smaller problem $(p\bmod i)^{-1}\bmod p$. Therefore, starting from $1^{-1}\bmod p=1$ and applying the formula successively for each $i$ yields the inverses of the first $n$ integers in $O(n)$ time.

A reference implementation follows:

// Precomputes modular inverses of all integers from 1 to n modulo prime p.
std::vector<int> precompute_inverses(int n, int p) {
  std::vector<int> res(n + 1);
  res[1] = 1;
  for (int i = 2; i <= n; ++i) {
    res[i] = (long long)(p - p / i) * res[p % i] % p;
  }
  return res;
}

# Precomputes modular inverses of all integers from 1 to n modulo prime p.
def precompute_inverses(n, p):
    res = [0] * (n + 1)
    res[1] = 1
    for i in range(2, n + 1):
        res[i] = (p - p // i) * res[p % i] % p
    return res

This algorithm applies only when the modulus is prime. For a non-prime modulus $m$, the $m\bmod i$ obtained in the recurrence is not guaranteed to be coprime to $m$, so the $(m\bmod i)^{-1}$ required by the recurrence may not exist. For example, let $m=8,i=3$. Then $m\bmod i = 2$, which has no inverse modulo $m$.

After obtaining this recurrence, a natural idea is to recursively find the inverse of any number $a$. At each recursive call, use the recurrence to reduce it to the inverse of the smaller remainder $p\bmod a$, stopping when the remainder becomes $1$. The complexity of this approach is not currently clear¹, so the conventional method described above is recommended.

Exercises

• LOJ 110 Modular Multiplicative Inverse
• LOJ 161 Modular Multiplicative Inverse 2
• LOJ 2605「NOIP2012」Congruence Equation
• Luogu P2054「AHOI2005」Shuffle
• LOJ 2034「SDOI2016」Permutation Counting

References and notes

• Modular multiplicative inverse - Wikipedia