Modular multiplicative inverse calculator


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: