Get reference code
Appearance
Sample
StudyMath

Modular Multiplicative Inverse

This calculator calculates modular multiplicative inverse of an given integer a modulo m
Timur2014-02-24 14:06:03

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

Modular Multiplicative InverseCreative Commons Attribution/Share-Alike License 3.0 (Unported)
 

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.

Request a calculator
View all calculators
(514 calculators in total. )

Comments