Modular Multiplicative Inverse Calculator

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.

Inverse Modulo Calculator

Integer

Modulo

Calculate

Modular Multiplicative Inverse

 

 Link  Save  Widget

Modular multiplicative inverse

The modular multiplicative inverse of an integer a modulo m is an integer b such that
,
It may be denoted as , 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:

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 . Since one can be divided without remainder only by one, the equation above has the solution only if .

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

That is

Thus, x indeed is the modular multiplicative inverse of a modulo m.