This calculator calculates the modular multiplicative inverse of a given integer a under modulo m:
\[x\equiv a^{-1} \pmod{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)\]