# Modular multiplicative inverse calculator

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

 a= m= x=

## Modular multiplicative Inverse

The inverse of an element $$x$$ is another element $$y$$ such that $$x\circ y = e$$, where $$e$$ is the neutral element. For example:

$\begin{array}{rl} x + y &= 0\Rightarrow y = -x\\ x \cdot y &= 1\Rightarrow y = x^{-1}\\ \end{array}$

In number theory and encryption often the inverse is needed under a modular ring. Less formal spoken, how can one divide a number under a modular relation? Here the multiplicative inverse comes in. The multiplicative inverse of an integer $$a$$ modulo $$m$$ exists if and only if $$a$$ and $$m$$ are coprime (i.e., if $$\gcd(a, m) = 1$$) and is an integer $$x$$ such that

$a x\equiv 1 \pmod{m}$

Dividing both sides by $$a$$ gives

$x\equiv a^{-1} \pmod{m}$

The solution can be found with the euclidean algorithm as follows. Lets take

$ax+by=1$

This is a linear diophantine equation with two unknowns, which solution should be a multiple of $$\gcd(a,b)$$

To calculate the modular inverse, the calculator uses this idea to find solutions to the Bezout identity using the EGCD:

$au+bv=\gcd(a,b)$