Modular Multiplicative Inverse Calculator

This inverse modulo calculator calculates the modular multiplicative inverse of a given integer a modulo m.

Multiplicative inverse vs. Modular multiplicative inverse warning

First of all, there is a multiplicative inverse or reciprocal for a number x, denoted by 1/x or x⁻¹, and it is not the same as modular multiplicative inverse. The reciprocal of a number x is a number, which, when multiplied by the original x, yields 1, called the multiplicative identity. You can find the reciprocal quite easily. For the fraction a/b, the multiplicative inverse is b/a. To find the multiplicative inverse of a real number, simply divide 1 by that number. I do not think any special calculator is needed in each of these cases. But the modular multiplicative inverse is a different thing, that's why you can see our inverse modulo calculator below. The theory can be found after the calculator.

PLANETCALC, Inverse Modulo Calculator

Inverse Modulo Calculator

Modular Multiplicative Inverse
9

Modular multiplicative inverse

The modular multiplicative inverse of an integer a modulo m is an integer b such that
ab \equiv 1 \pmod m,
It may be denoted as a^{-1}, where the fact that the inversion is m-modular is implicit.

The multiplicative inverse of a modulo m exists if and only if 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. Zero has no modular multiplicative inverse.

The modular multiplicative inverse of a modulo m can be found with the Extended Euclidean algorithm.

To show this, let's look at this equation:

ax + my = 1

This is a linear diophantine equation with two unknowns; refer to Linear Diophantine Equations Solver. To have the solution, the right part of the linear diophantine equation should be a multiple of the gcd(a,m). Since one can be divided without remainder only by one, the equation above has the solution only if gcd(a,m)=1.

The solution can be found with the Extended Euclidean algorithm. Once we have the solution, our x is the modular multiplicative inverse of a modulo m. Rewrite the above equation like that
ax - 1 = (-y)m
That is
ax \equiv 1 \pmod m
Thus, x indeed is the modular multiplicative inverse of a modulo m.

URL copied to clipboard
PLANETCALC, Modular Multiplicative Inverse Calculator

Comments