Modular Inverse Finder — Drag a and m, Watch the Inverse Appear (or Fail)

In the integers, most numbers do not have a multiplicative inverse — 3 has no integer b with 3b = 1. In modular arithmetic, some do and some don't, and the condition for "does" is beautifully simple: a has a multiplicative inverse modulo m if and only if \gcd(a, m) = 1. The visualisation you need is a drag-pair: slide a and m around, watch \gcd(a, m) update, and see either a unique inverse b appear (when the gcd is 1) or a blank answer (when it is not). Getting this reflex is essential because modular inverses underpin half of the techniques in modular arithmetic — dividing in a congruence, solving linear equations mod n, Chinese Remainder Theorem constructions, even the core of RSA encryption.

What a modular inverse is

Modular inverse

Given positive integers a and m, a modular inverse of a modulo m is an integer b with

a \cdot b \equiv 1 \pmod m.

If such a b exists, it is unique modulo m. It is often written a^{-1} \pmod m.

The inverse is the modular analogue of "one over a". In modular world, though, "one over" means a whole number that multiplies a to give 1 (mod m). So 3^{-1} \pmod 7 is asking: which integer b satisfies 3b \equiv 1 \pmod 7? Test small values: 3 \cdot 1 = 3, 3 \cdot 2 = 6, 3 \cdot 3 = 9 \equiv 2, 3 \cdot 4 = 12 \equiv 5, 3 \cdot 5 = 15 \equiv 1. So 3^{-1} \equiv 5 \pmod 7.

When does an inverse exist?

Not always. Try to find 3^{-1} \pmod 6: 3 \cdot 1 = 3, 3 \cdot 2 = 6 \equiv 0, 3 \cdot 3 = 9 \equiv 3, 3 \cdot 4 = 12 \equiv 0, 3 \cdot 5 = 15 \equiv 3. The values cycle through \{0, 3\} — never hitting 1. No inverse exists.

The difference: \gcd(3, 7) = 1 (inverse exists) versus \gcd(3, 6) = 3 \neq 1 (no inverse).

Inverse-existence criterion

a has a multiplicative inverse modulo m if and only if \gcd(a, m) = 1.

The reason flows straight from Bezout's identity. If \gcd(a, m) = 1, then there exist integers x, y with ax + my = 1. Reading both sides mod m gives ax \equiv 1 \pmod m, so b = x is the inverse. Conversely, if ab \equiv 1 \pmod m, then ab = 1 + km for some integer k, so ab - km = 1, meaning \gcd(a, m) \mid 1, i.e. \gcd(a, m) = 1.

Interactive: drag a and m

Drag the red dot to change $a$ (from $1$ to $14$) and the blue dot to change $m$ (from $2$ to $15$). The display updates $\gcd(a, m)$ and either shows the unique inverse $b$ with $ab \equiv 1 \pmod m$, or reports "no inverse" if $\gcd \neq 1$. Try $(a, m) = (3, 7)$: $\gcd = 1$, inverse is $5$. Try $(3, 6)$: $\gcd = 3$, no inverse.

What the tool reveals

Play with the tool for a minute and two big patterns emerge.

Pattern 1: primes m always give inverses (except for a \equiv 0). If m is prime, every integer a with 1 \leq a < m has \gcd(a, m) = 1, so every non-zero a has an inverse. This is why \mathbb{Z}/p\mathbb{Z} for prime p is a field — every non-zero element is invertible.

Pattern 2: composite m has gaps. For m = 12, the elements with inverses are exactly \{1, 5, 7, 11\} — the residues coprime to 12. The others (2, 3, 4, 6, 8, 9, 10) have \gcd > 1 with 12 and no inverse. The count of invertible residues mod m is Euler's totient function \phi(m): \phi(12) = 4.

How the inverse is actually computed

Brute force ("try b = 1, 2, 3, \ldots") works for small m. For large m, use the extended Euclidean algorithm. Running it on (a, m) with \gcd(a, m) = 1 gives integers x, y with ax + my = 1, and then x \bmod m is the inverse.

Example: find 7^{-1} \pmod {26}.

26 = 3 \cdot 7 + 5, \quad 7 = 1 \cdot 5 + 2, \quad 5 = 2 \cdot 2 + 1, \quad 2 = 2 \cdot 1 + 0.

So \gcd(7, 26) = 1. Back-substituting:

1 = 5 - 2 \cdot 2 = 5 - 2(7 - 5) = 3 \cdot 5 - 2 \cdot 7 = 3(26 - 3 \cdot 7) - 2 \cdot 7 = 3 \cdot 26 - 11 \cdot 7.

So 1 = -11 \cdot 7 + 3 \cdot 26, meaning 7 \cdot (-11) \equiv 1 \pmod {26}. Adjust to positive: -11 \equiv 15 \pmod {26}. So 7^{-1} \equiv 15 \pmod {26}. Check: 7 \cdot 15 = 105 = 4 \cdot 26 + 1.

This is exactly what the tool does under the hood (but with a simple brute search for small values).

Why modular inverses matter

They are the engine of several techniques.

Dividing in a congruence. You cannot divide both sides of a congruence by any number — only by one that is coprime to the modulus. "Divide by a" really means "multiply by a^{-1} \pmod m". The inverse makes division well-defined.

Solving linear equations mod m. To solve ax \equiv c \pmod m, multiply both sides by a^{-1} (if it exists): x \equiv a^{-1} c \pmod m. No inverse means the equation might have no solutions or many.

Chinese Remainder Theorem construction. The standard CRT formula involves m_i^{-1} \pmod{n_i} terms. Without inverses, CRT would be useless.

RSA public-key cryptography. The public and private keys in RSA are a pair of modular inverses mod \phi(n). The entire security of the system rides on the fact that finding the inverse is easy (with the right secret) but finding \phi(n) without that secret is hard.

A worked example

Problem: Solve $4x \equiv 7 \pmod {15}$

Step 1: find 4^{-1} \pmod {15}. Check \gcd(4, 15) = 1 — yes, since 4 = 2^2 and 15 = 3 \cdot 5 share no prime. Inverse exists.

Brute search (or extended Euclidean): 4 \cdot 1 = 4, 4 \cdot 2 = 8, 4 \cdot 3 = 12, 4 \cdot 4 = 16 \equiv 1 \pmod {15}. So 4^{-1} \equiv 4 \pmod {15}.

Why: 4^{-1} happens to equal 4 itself here — a coincidence, not a rule.

Step 2: multiply both sides of 4x \equiv 7 \pmod {15} by 4:

x \equiv 4 \cdot 7 = 28 \equiv 13 \pmod {15}.

Check. 4 \cdot 13 = 52 = 3 \cdot 15 + 7, so 4 \cdot 13 \equiv 7 \pmod {15}. Solved.

And a case where inverses fail:

Problem: Solve $6x \equiv 4 \pmod {15}$

Check \gcd(6, 15) = 3 \neq 1. So 6^{-1} \pmod {15} does not exist — the single-inverse trick fails.

But: \gcd(6, 15) = 3, and 3 \mid 4? 4 / 3 is not an integer, so no solution exists at all.

Why: a solution to 6x \equiv 4 \pmod {15} requires 15 \mid (6x - 4), hence 3 \mid (6x - 4). But 3 \mid 6x, so 3 \mid 4, which is false.

If instead the problem had been 6x \equiv 3 \pmod {15}: 3 \mid 3, so there are solutions. Divide through by \gcd = 3: 2x \equiv 1 \pmod 5, whose inverse-based solution is x \equiv 3 \pmod 5. Lifting back to mod 15: x \in \{3, 8, 13\} — three solutions, not one.

The gcd tells you three things in one go: whether a unique inverse exists (\gcd = 1), whether the linear equation has any solutions (\gcd \mid c), and how many solutions there are (\gcd of them, spread evenly mod m).

The one-line takeaway

a has a multiplicative inverse modulo m if and only if \gcd(a, m) = 1. Drag the inverse finder: when \gcd = 1, a unique b with ab \equiv 1 \pmod m appears; when \gcd > 1, no inverse exists and some linear equations have zero or many solutions instead of one.