This calculator calculates modular multiplicative inverse of an given integer a modulo m. The theory is below the calculator.
Save the calculation to reuse next time, to extension embed in your website or share share with friends.
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.