homechevron_rightStudychevron_rightMath

Modular Multiplicative Inverse

This calculator calculates modular multiplicative inverse of an given integer a modulo m

This calculator calculates modular multiplicative inverse of an given integer a modulo m. The theory is below the calculator.

PLANETCALC, Modular Multiplicative Inverse

Modular Multiplicative Inverse

Modular Multiplicative Inverse
 
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

ab \equiv 1 \pmod m,

It maybe noted a^{-1}, 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:

ax + my = 1

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 {\rm gcd}(a,m)=1.

The solution can be found with the Extended Euclidean algorithm. The modulo operation on both parts of equation gives us

ax = 1 \pmod m

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

Comments