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.
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.
Comentários