What is a modular inverse?
The modular multiplicative inverse of an integer a modulo m is an integer x such that \((a \cdot x) \bmod m = 1\). It is the "division" operation of modular arithmetic and is central to number theory, the RSA cryptosystem, and many coding-theory algorithms. This calculator finds x using the extended Euclidean algorithm.
How to use this calculator
Enter the number a and the modulus m (with m ≥ 2). The tool returns the smallest non-negative inverse x in the range 0 ≤ x < m, confirms whether an inverse exists, and shows gcd(a, m). If gcd(a, m) ≠ 1, no inverse exists and the result is reported as "None".
The formula explained
An inverse exists only when \(\gcd(a, m) = 1\), i.e. a and m are coprime. The extended Euclidean algorithm finds integers x and y satisfying \(a \cdot x + m \cdot y = \gcd(a, m)\). When the gcd is 1, reducing x modulo m gives the inverse:
The result is normalized to a positive value by adding m if it is negative.
Worked example
Find the inverse of 3 modulo 11. We need x with \(3x \equiv 1 \pmod{11}\). Testing, \(3 \times 4 = 12 = 11 + 1\), so \(12 \bmod 11 = 1\). Therefore \(x = 4\). The extended Euclidean algorithm returns the same value, and \(\gcd(3, 11) = 1\), confirming the inverse exists.
FAQ
When does no inverse exist? When a and m share a common factor greater than 1 — for example 4 modulo 6 (gcd = 2) has no inverse.
Does m have to be prime? No. m can be any integer ≥ 2; only coprimality of a and m matters.
What range is the answer in? The inverse is given as the smallest non-negative residue, between 0 and m − 1.
