Inverse Modulo Calculator

Inverse Modulo Calculator

Growing AI Skill PRO

Enter Calculation

Results

Modular Inverse
2,753
x such that (a·x) mod m = 1
Inverse exists Yes
gcd(a, m) 1

Formula

a·x≡1(modm)⟹x=a−1modm\text{a} \cdot x \equiv 1 \pmod{\text{m}} \quad\Longrightarrow\quad x = \text{a}^{-1} \bmod \text{m}
Usage stats

Advertisement

Report an error on this page

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.

Number line wrapping around a circular clock-like modulus ring showing a times x landing on 1
A modular inverse x maps a back to 1 when multiplied, wrapping around the modulus m.

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:

$$\text{a} \cdot x \equiv 1 \pmod{\text{m}} \quad\Longrightarrow\quad x = \text{a}^{-1} \bmod \text{m}$$

The result is normalized to a positive value by adding m if it is negative.

Advertisement
Flat flowchart of the extended Euclidean algorithm steps producing gcd and coefficients
The extended Euclidean algorithm yields coefficients that give the inverse when gcd(a, m) = 1.

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.

Step-by-Step: Extended Euclidean Algorithm by Hand

The modular inverse of a modulo m is the number x with \(a \cdot x \equiv 1 \pmod{m}\). It exists only when \(\gcd(a, m) = 1\). The extended Euclidean algorithm finds it in three steps.

  1. Repeated division. Divide m by a, then divide the previous divisor by the remainder, and so on, until the remainder is 0. The last nonzero remainder is the gcd. If it is not 1, no inverse exists.
  2. Express 1 as a combination. Work backwards (back-substitution), or track coefficients as you go, to write \(1 = a \cdot x + m \cdot y\). This is the Bézout identity.
  3. Reduce x. Take \(x \bmod m\). If x is negative, add m (repeat if necessary) to land in the range 0 to m − 1.

Worked example: a = 7, m = 40.

Step Division Quotient q Remainder
1 40 = 5·7 + 5 5 5
2 7 = 1·5 + 2 1 2
3 5 = 2·2 + 1 2 1
4 2 = 2·1 + 0 2 0

The last nonzero remainder is 1, so \(\gcd(7, 40) = 1\) and an inverse exists.

Back-substitution:

$$1 = 5 - 2\cdot 2 = 5 - 2(7 - 5) = 3\cdot 5 - 2\cdot 7 = 3(40 - 5\cdot 7) - 2\cdot 7 = 3\cdot 40 - 17\cdot 7$$

So \(7 \cdot (-17) + 40 \cdot 3 = 1\), which gives \(x = -17\).

Iterative check (coefficient t of a): start with \(t_0 = 0\) (for m = 40) and \(t_1 = 1\) (for a = 7), then use \(t_{k+1} = t_{k-1} - q_k \, t_k\).

Remainder q used t
40 – 0
7 – 1
5 5 0 − 5·1 = −5
2 1 1 − 1·(−5) = 6
1 2 −5 − 2·6 = −17

The row where the remainder reaches 1 gives \(t = -17\). Reduce it: \(-17 + 40 = \)23.

Verification: \(7 \cdot 23 = 161 = 4 \cdot 40 + 1\), so \(161 \bmod 40 = 1\). ✓

The same method works for larger numbers. For a = 17, m = 3120 it gives x = 2753, because \(17 \cdot 2753 = 46801 = 15 \cdot 3120 + 1\). This pair is a classic textbook RSA example.

Example Inputs and Their Inverses

Each inverse below satisfies \((a \cdot x) \bmod m = 1\). When \(\gcd(a, m) > 1\), no inverse exists.

a m gcd(a, m) Inverse x Check
3 11 1 4 3·4 = 12 = 1·11 + 1
7 26 1 15 7·15 = 105 = 4·26 + 1
5 12 1 5 5·5 = 25 = 2·12 + 1
10 17 1 12 10·12 = 120 = 7·17 + 1
17 3120 1 2753 17·2753 = 46801 = 15·3120 + 1
4 6 2 None 4x mod 6 is always even, never 1
6 9 3 None 6x mod 9 is always a multiple of 3, never 1

Notice that 5 is its own inverse modulo 12. In general, \(x^2 \equiv 1 \pmod{m}\) has solutions other than 1, so some numbers are self-inverse.

Advertisement

Key Terms: Coprime, GCD, Congruence and Residue

  • Modulus (m): the positive integer at which values wrap around, as on a clock face.
  • Congruence (≡): \(a \equiv b \pmod{m}\) means m divides \(a - b\), so a and b leave the same remainder when divided by m.
  • GCD: the greatest common divisor, the largest integer that divides both numbers.
  • Coprime (relatively prime): two integers whose gcd is 1. This is exactly the condition for a modular inverse to exist.
  • Bézout identity: for integers a and m there are integers x and y with \(a \cdot x + m \cdot y = \gcd(a, m)\). When the gcd is 1, reducing this equation modulo m gives \(a \cdot x \equiv 1\), so x is the inverse.
  • Residue class: the set of all integers sharing the same remainder modulo m. The inverse is unique as a residue class, and the calculator reports the representative from 0 to m − 1.
  • Modular multiplicative inverse: the residue \(x = a^{-1} \bmod m\) with \(a \cdot x \equiv 1 \pmod{m}\).

Euler's theorem: if \(\gcd(a, m) = 1\), then \(a^{\varphi(m)} \equiv 1 \pmod{m}\), where \(\varphi\) is Euler's totient function. So the inverse can also be computed as \(a^{\varphi(m)-1} \bmod m\).

Fermat's little theorem: when m = p is prime, \(\varphi(p) = p - 1\), so \(a^{-1} \equiv a^{p-2} \pmod{p}\) for any a not divisible by p. Example: \(3^{9} = 19683 = 1789 \cdot 11 + 4\), so \(3^{-1} \equiv 4 \pmod{11}\), matching the table above. The power formula needs the factorization of m (to find \(\varphi\)), while the extended Euclidean algorithm does not, so it is usually the faster method for general moduli.

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.

Last updated:

Most popular in Math and Statistics

View all Math and Statistics calculators