# Modular multiplicative inverse calculator

 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$$ 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, which is used for the calculator.

## How does the calculator work?

To calculate the modular inverse, the calculator uses the extended euclidean algorithm which find solutions to the Bezout identity:

$au+bv=GCD(a,b)$