# 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)\]