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

Timur

Created: 2014-02-24 14:06:03, Last updated: 2021-10-19 09:34:06
Creative Commons Attribution/Share-Alike License 3.0 (Unported)

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.

PLANETCALC, Inverse Modulo Calculator

Inverse Modulo Calculator

Modular Multiplicative Inverse
 

Modular multiplicative inverse

The modular multiplicative inverse of an integer a modulo m is an integer b such that
ab \equiv 1 \pmod m,
It may be denoted as 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 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 gcd(a,m). Since one can be divided without remainder only by one, the equation above has the solution only if gcd(a,m)=1.

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
ax - 1 = (-y)m
That is
ax \equiv 1 \pmod m
Thus, x indeed is the modular multiplicative inverse of a modulo m.

URL copied to clipboard
PLANETCALC, Modular Multiplicative Inverse Calculator

Comments