Modular Multiplicative Inverse Calculator

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

Esta página existe graças aos esforços das seguintes pessoas:

Timur

Timur

Criado: 2014-02-24 14:06:03, Ultima atualização: 2021-10-19 09:34:06

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 copiado para a área de transferência
PLANETCALC, Modular Multiplicative Inverse Calculator

Comentários