Modular Multiplicative Inverse Calculator
This inverse modulo calculator calculates the modular multiplicative inverse of a given integer a modulo m.
This page exists due to the efforts of the following people:
 | Timur
|
This content is licensed under Creative Commons Attribution/Share-Alike License 3.0 (Unported). That means you may freely redistribute or modify this content under the same license conditions and must attribute the original author by placing a hyperlink from your site to this work https://planetcalc.com/3311/. Also, please do not modify any references to the original work (if any) contained in this content.
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
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.
Similar calculators
- • Linear Diophantine Equations Solver
- • Extended Euclidean algorithm
- • The greatest common divisor of two integers
- • The greatest common divisor and the least common multiple of two integers
- • Solution of nonhomogeneous system of linear equations using matrix inverse
- • Algebra section ( 112 calculators )
Comments