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.
This calculator calculates modular multiplicative inverse of an given integer a modulo m. The theory is below the calculator.
The modular multiplicative inverse of an integer a modulo m is an integer b such that
It maybe noted , 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 linear diophantine equation with two unknowns, refer to Linear Diophantine equations. Since one can be divided without reminder only by one, this equation has the solution only if .
The solution can be found with the Extended Euclidean algorithm. The modulo operation on both parts of equation gives us
Thus, x is the modular multiplicative inverse of a modulo m.