Modular multiplicative inverse

The modular multiplicative inverse of an integer a modulo m is an integer x such that

$a^{-1}\equiv x{\pmod {m}}.$

That is, it is the multiplicative inverse in the ring of integers modulo m. This is equivalent to

$ax\equiv aa^{-1}\equiv 1{\pmod {m}}.$

The multiplicative inverse of a modulo m exists iff a and m are coprime (i.e., if gcd(a, m) = 1). If the modular multiplicative inverse of a modulo m exists, the operation of division by a modulo m can be defined as multiplying by the inverse, which is in essence the same concept as division in the field of reals.

Explanation

When the inverse exists, it is always unique in Z_m where m is the modulus. Therefore, the x that is selected as the modular multiplicative inverse is generally a member of Z_m for most applications.

For example,

$3^{-1}\equiv x{\pmod {11}}$

yields

$3x\equiv 1{\pmod {11}}$

The smallest x that solves this congruence is 4; therefore, the modular multiplicative inverse of 3 (mod 11) is 4. However, another x that solves the congruence is 15 (easily found by adding m, which is 11, to the found inverse).

Computation

Extended Euclidean Algorithm

The modular multiplicative inverse of a modulo m can be found with the extended Euclidean algorithm. The algorithm finds solutions to Bézout's identity

$ax+by=\gcd(a,b)\,$

where a, b are given and x, y, and gcd(a, b) are the integers that the algorithm discovers. So, since the modular multiplicative inverse is the solution to

$ax\equiv 1{\pmod {m}},$

by the definition of congruence, m | ax - 1, which means that m is a divisor of ax - 1. This, in turn, means that

$ax-1=qm.\,$

Rearranging produces

$ax-qm=1,\,$

with a and m given, x the inverse, and q an integer multiple that will be discarded. This is the exact form of equation that the extended Euclidean algorithm solves—the only difference being that gcd(a, m)=1 is predetermined instead of discovered. Thus, a needs to be coprime to the modulus, or the inverse won't exist. The inverse is x, and q is discarded.

This algorithm runs in time O(log(m)²), assuming |a|<m, and is generally more efficient than exponentiation.

Using Euler's theorem

As an alternative to the extended Euclidean algorithm, Euler's theorem may be used to compute modular inverse:

According to Euler's theorem, if a is coprime to m, that is, gcd(a, m) = 1, then

$a^{\varphi (m)}\equiv 1{\pmod {m}}$

where φ(m) is Euler's totient function. This follows from the fact that a belongs to the multiplicative group (Z/mZ)^* iff a is coprime to m. Therefore the modular multiplicative inverse can be found directly:

$a^{\varphi (m)-1}\equiv a^{-1}{\pmod {m}}$

This method is generally slower than the extended Euclidean algorithm, but is sometimes used when an implementation for modular exponentiation is already available. Some disadvantages of this method include:

• the required knowledge of φ(m), whose most efficient computation requires m's factorization. Factorization is widely believed to be a mathematically hard problem. However, calculating φ(m) is trivial in some common cases such as when m is known to be prime or a power of 2.
• exponentiation. Though it can be implemented more efficiently using modular exponentiation, which is a form of binary exponentiation, it is still a taxing operation with computational complexity O(log φ(m)) = O(log m).

Fermat's little theorem

Fermat's little theorem can be used to calculate the modular inverse when m is a prime number. From the theorem:

$a^{m-1}\equiv 1{\pmod {m}}\,\!$

$a^{m-2}a\equiv 1{\pmod {m}}\,\!$

Therefore, a^m-2 is the modular multiplicative inverse of a if and only if m is prime. This method still requires using modular exponentiation and is only specific to prime modulus.

Implementation in Python

def extended_gcd(a, b):
    x, last_x = 0, 1
    y, last_y = 1, 0
    
    while b:
        quotient = a // b
        a, b = b, a % b
        x, last_x = last_x - quotient*x, x
        y, last_y = last_y - quotient*y, y
    
    return (last_x, last_y, a)

def inverse_mod(a, m):
    x, q, gcd = extended_gcd(a, m)
    
    if gcd == 1:
        # x is the inverse, but we want to be sure a positive number is returned.
        return (x + m) % m
    else:
        # if gcd != 1 then a and m are not coprime and the inverse does not exist.
        return None

Implementation in C

int extended_gcd (int * a, int b) {
    int x = 0, lastx = 1;
    int y = 1, lasty = 0;
    int temp;
    div_t q;

    while (b) {
        q = div (*a, b);
        *a = b;
        b = q.rem;

        temp = x;
        x = lastx - q.quot * x;
        lastx = temp;

        temp = y;
        y = lasty - q.quot * y;
        lasty = temp;
    }

    return lastx;
}

int inverse_mod (int a, int m) {
    int x = extended_gcd (&a, m);
    if (a)
        return (x + m) % m;

    return 0;
}

Example

>>> a = 1234
>>> m = 9997
>>> inverse_mod(a, m)
3119
>>> (a * inverse_mod(a, m)) % m
1

See also

• Inversive congruential generator
• Modular arithmetic
• Number theory
• Public-key cryptography