Modular Multiplicative Inverse Calculator

What is a Modular Multiplicative Inverse?

In modular arithmetic, the modular multiplicative inverse of an integer $a$ modulo $m$ is an integer $x$ that satisfies the linear congruence equation:

$$a \cdot x \equiv 1 \pmod m$$

This equation is equivalent to saying that the remainder of the product $a \cdot x$ when divided by $m$ is equal to $1$. The value of $x$ is typically chosen from the range of integers $0 \le x < m$.

Unlike regular division where every non-zero number has a reciprocal (multiplicative inverse), a modular multiplicative inverse of $a$ modulo $m$ exists if and only if $a$ and $m$ are coprime. This means that their greatest common divisor is 1:

$$\gcd(a, m) = 1$$

How to Calculate the Modular Inverse Using the Extended Euclidean Algorithm

The most efficient way to find the modular multiplicative inverse is using the Extended Euclidean Algorithm. This algorithm not only computes the greatest common divisor of $a$ and $m$, but also computes integers $x$ and $y$ that satisfy Bézout's identity:

$$a \cdot x + m \cdot y = \gcd(a, m)$$

When $a$ and $m$ are coprime, the equation becomes:

$$a \cdot x + m \cdot y = 1$$

Taking this equation modulo $m$, we get:

$$a \cdot x \equiv 1 \pmod m$$

Thus, the coefficient $x$ returned by the Extended Euclidean Algorithm is the modular multiplicative inverse of $a$ modulo $m$. If the algorithm yields a negative value for $x$, we add $m$ to get a positive representative in the range $[0, m - 1]$.

Interactive Examples and Applications

Modular inverses have wide applications in mathematics, cryptography (especially RSA encryption), and computer science. For instance, they are used to solve systems of linear congruences via the Chinese Remainder Theorem Calculator or to perform basic division in modular arithmetic using a Modulo Calculator.