A multiplicative inverse of a modulo n does not always exist - for which a does it exist, and why?

middlemust knowfreq 62%

answer

not every value can be undone
a shared factor is the blocker
coprime to the modulus
gcd(a, n) = 1, nothing else
Bezout: a*x + n*y = 1

basics

~20 s

A value a has a multiplicative inverse modulo n exactly when gcd(a, n) = 1. If they share a factor g > 1, every product a*x reduced modulo n is a multiple of g, and 1 never is.

solid answer

~50 s

An inverse of a modulo n is a residue x with a*x = 1 (mod n) - not a fraction, a residue. It exists if and only if gcd(a, n) = 1. The forward direction is the extended Euclidean identity: coprimality gives integers with a*x + n*y = 1, and reducing modulo n kills the n*y term, leaving a*x = 1. The reverse direction is just as concrete: write g = gcd(a, n), a = g*a', n = g*n'. Then a*x - k*n = g*(a'*x - k*n') for every integer k, so every value a*x can take modulo n is a multiple of g. When g > 1, the value 1 is not among them, so no x works. Modulo a prime p, every nonzero residue is coprime to p, so every one of them is invertible.

An inverse of `a` modulo `n` is a residue `x` with `a*x = 1 (mod n)` - not a fraction, a residue. It exists if and only if `gcd(a, n) = 1`. The forward direction is the extended Euclidean identity: coprimality gives integers with `a*x + n*y = 1`, and reducing modulo `n` kills the `n*y` term, leaving `a*x = 1`. The reverse direction is just as concrete: write `g = gcd(a, n)`, `a = g*a'`, `n = g*n'`. Then `a*x - k*n = g*(a'*x - k*n')` for every integer `k`, so every value `a*x` can take modulo `n` is a multiple of `g`. When `g > 1`, the value 1 is not among them, so no `x` works. Modulo a prime `p`, every nonzero residue is coprime to `p`, so every one of them is invertible.

code

pseudocode · 12 lines

pseudocode

// window [s, s+L) of stream a, base b, modulus n
// fingerprint h = sum over i in [s, s+L) of a[i] * b^i   (mod n)

advance(h, s):
    h = (h - a[s]     * powmod(b, s,   n)) mod n   // drop oldest term
    h = (h + a[s + L] * powmod(b, s+L, n)) mod n   // add newest term
    return h

normalize(h, s):
    // strip the position so windows at different offsets compare
    binv = inverse(b, n)          // requires gcd(b, n) = 1
    return (h * powmod(binv, s, n)) mod n

go deeper

for a junior

Remember the headline: a value can be inverted modulo n only when it shares no factor with n, and modulo a prime every nonzero value qualifies. Inverse means a residue, never a fraction.

for a middle

Be ready to argue both directions: coprimality gives the Bezout identity and therefore an inverse, and a shared factor g forces every product to be a multiple of g, so 1 is unreachable.

for a senior

Show where the check belongs in a running system: validate coprimality where the base or divisor is chosen, and treat 'not invertible' as a real branch rather than an impossible one.

for a principal

The lever is the modulus itself. Choosing a prime makes every nonzero value invertible and removes a whole class of latent failure; choosing a composite one buys cheaper reduction and takes on a constraint every caller must now respect.

What "inverse modulo n" means

Arithmetic modulo n works with the residues 0, 1, ..., n-1, where two integers are the same element when they differ by a multiple of n. Addition and multiplication carry over from the integers. Division does not come along for free: there is no residue called 1/a. What can exist is a multiplicative inverse - a residue x such that

a * x = 1 (mod n)

When such an x exists it is unique among the residues, and "dividing by a" modulo n means multiplying by x.

The condition, both directions

The rule is short: a has an inverse modulo n exactly when gcd(a, n) = 1 - when a and the modulus are coprime. Neither the size of a nor the size of n matters, and a being prime does not help unless it misses the modulus' factors.

Coprime implies invertible. The extended Euclidean identity says that for any a and n there are integers x, y with a*x + n*y = gcd(a, n). If the gcd is 1, reduce that equation modulo n: the term n*y is a multiple of the modulus and vanishes, leaving a*x = 1 (mod n). So x, reduced into the residue range, is the inverse.
Sharing a factor implies not invertible. Let g = gcd(a, n) > 1, and write a = g*a' and n = g*n'. Every integer of the form a*x - k*n equals g*(a'*x - k*n'), so every value that a*x can take modulo n is a multiple of g. Since g > 1, the residue 1 is not a multiple of g, and no x can reach it.

That second argument also explains the shape of the damage: the map x -> a*x (mod n) is not onto. It lands only on the multiples of g, and hits each of them g times, so it is not reversible in any sense - information is destroyed, not merely scrambled.

What this looks like for concrete moduli

modulus `n`	residues with an inverse	residues with none
10	1, 3, 7, 9	0, 2, 4, 5, 6, 8
12	1, 5, 7, 11	0, 2, 3, 4, 6, 8, 9, 10
16	all eight odd residues	0 and the seven even ones
13 (prime)	all twelve nonzero residues	0 only

Two patterns fall out. A prime modulus is the generous case: the only residue coprime to p that fails is 0, so every nonzero residue is invertible. A power-of-two modulus is exactly the odd residues - half of them - because the only prime factor to collide with is 2.

Why a rolling fingerprint depends on it

A rolling fingerprint over a sliding window treats the window's bytes as the coefficients of a polynomial in a base b, evaluated modulo n. In the position-indexed form, the byte at absolute stream position i contributes a[i] * b^i, so advancing the window subtracts the oldest term and adds the newest one. To compare two windows at different positions, the service has to strip the position out - multiply by b raised to a negative power, which means multiplying by the inverse of b modulo n.

That inverse either exists or the design does not work:

If gcd(b, n) = 1, the shift is reversible and two windows are comparable no matter where they sit in the stream.
If b and n share a factor, no amount of implementation care recovers the shift; the fingerprint collapses onto the multiples of that factor and the whole comparison becomes weaker.
A base picked by hashing configuration or user input is a base nobody checked - the coprimality condition has to be enforced where the base is chosen, not where it is used.

Where engineers go wrong

Assuming every nonzero residue is invertible. That is true only for a prime modulus. With a composite one, a large fraction of residues have no inverse at all.
Confusing the two inverses. The additive inverse of a modulo n is n - a and always exists. The multiplicative one is the conditional one.
Treating a being prime as sufficient. 3 has no inverse modulo 12, because 3 divides 12.
Reaching for real-number intuition. 1/a rounded, truncated or computed in floating point has nothing to do with the residue that satisfies a*x = 1 (mod n).

The practical upshot is a one-line guard wherever a modular division is about to happen: compute the gcd with the modulus first, and treat "not coprime" as a real branch, not an impossible one.

## What "inverse modulo n" means Arithmetic modulo `n` works with the **residues** `0, 1, ..., n-1`, where two integers are the same element when they differ by a multiple of `n`. Addition and multiplication carry over from the integers. Division does not come along for free: there is no residue called `1/a`. What can exist is a **multiplicative inverse** - a residue `x` such that `a * x = 1 (mod n)` When such an `x` exists it is unique among the residues, and "dividing by `a`" modulo `n` means multiplying by `x`. ## The condition, both directions The rule is short: **`a` has an inverse modulo `n` exactly when `gcd(a, n) = 1`** - when `a` and the modulus are **coprime**. Neither the size of `a` nor the size of `n` matters, and `a` being prime does not help unless it misses the modulus' factors. 1. **Coprime implies invertible.** The extended Euclidean identity says that for any `a` and `n` there are integers `x, y` with `a*x + n*y = gcd(a, n)`. If the gcd is 1, reduce that equation modulo `n`: the term `n*y` is a multiple of the modulus and vanishes, leaving `a*x = 1 (mod n)`. So `x`, reduced into the residue range, is the inverse. 2. **Sharing a factor implies not invertible.** Let `g = gcd(a, n) > 1`, and write `a = g*a'` and `n = g*n'`. Every integer of the form `a*x - k*n` equals `g*(a'*x - k*n')`, so **every value that `a*x` can take modulo `n` is a multiple of `g`**. Since `g > 1`, the residue 1 is not a multiple of `g`, and no `x` can reach it. That second argument also explains the shape of the damage: the map `x -> a*x (mod n)` is not onto. It lands only on the multiples of `g`, and hits each of them `g` times, so it is not reversible in any sense - information is destroyed, not merely scrambled. ## What this looks like for concrete moduli | modulus `n` | residues with an inverse | residues with none | |---|---|---| | 10 | 1, 3, 7, 9 | 0, 2, 4, 5, 6, 8 | | 12 | 1, 5, 7, 11 | 0, 2, 3, 4, 6, 8, 9, 10 | | 16 | all eight odd residues | 0 and the seven even ones | | 13 (prime) | all twelve nonzero residues | 0 only | Two patterns fall out. A **prime modulus** is the generous case: the only residue coprime to `p` that fails is 0, so every nonzero residue is invertible. A **power-of-two modulus** is exactly the odd residues - half of them - because the only prime factor to collide with is 2. ## Why a rolling fingerprint depends on it A rolling fingerprint over a sliding window treats the window's bytes as the coefficients of a polynomial in a base `b`, evaluated modulo `n`. In the position-indexed form, the byte at absolute stream position `i` contributes `a[i] * b^i`, so advancing the window subtracts the oldest term and adds the newest one. To compare two windows at *different* positions, the service has to strip the position out - multiply by `b` raised to a negative power, which means multiplying by the **inverse of `b` modulo `n`**. That inverse either exists or the design does not work: - If `gcd(b, n) = 1`, the shift is reversible and two windows are comparable no matter where they sit in the stream. - If `b` and `n` share a factor, no amount of implementation care recovers the shift; the fingerprint collapses onto the multiples of that factor and the whole comparison becomes weaker. - A base picked by hashing configuration or user input is a base nobody checked - the coprimality condition has to be enforced where the base is chosen, not where it is used. ## Where engineers go wrong - **Assuming every nonzero residue is invertible.** That is true only for a prime modulus. With a composite one, a large fraction of residues have no inverse at all. - **Confusing the two inverses.** The **additive** inverse of `a` modulo `n` is `n - a` and always exists. The multiplicative one is the conditional one. - **Treating `a` being prime as sufficient.** 3 has no inverse modulo 12, because 3 divides 12. - **Reaching for real-number intuition.** `1/a` rounded, truncated or computed in floating point has nothing to do with the residue that satisfies `a*x = 1 (mod n)`. The practical upshot is a one-line guard wherever a modular division is about to happen: compute the gcd with the modulus first, and treat "not coprime" as a real branch, not an impossible one.

How many residues modulo 12 have a multiplicative inverse, and which are they?
Four: 1, 5, 7 and 11 - exactly the residues sharing no factor with 12. Everything even shares the factor 2, and 3, 6 and 9 share the factor 3, so eight of the twelve residues have no inverse. The pattern is why a composite modulus is a much less forgiving choice than a prime one.
If gcd(a, n) = g > 1, what concretely goes wrong when you try to solve a*x = 1 (mod n)?
Write a = g*a' and n = g*n'. Then a*x - k*n = g*(a'*x - k*n') for every k, so every value a*x can take modulo n is a multiple of g. The residue 1 is not one of them, so the equation has no solution. The same computation shows the map x -> a*x lands on only n/g distinct residues, each hit g times.
Does a larger modulus make inverses more likely to exist?
No - only the shared factors matter. 2 has no inverse modulo a modulus of two billion if that modulus is even, while 2 has an inverse modulo the tiny prime 7. What raises the fraction of invertible residues is a modulus with few prime factors; a prime modulus makes every nonzero residue invertible regardless of size.

Two meshed gears only cycle through every relative position when their tooth counts share no common factor; if both counts are even, half the positions are unreachable forever. Coprimality with the modulus is the same condition.

saying these in an interview costs you the question

Thinks every nonzero residue is invertible modulo any n
Says the inverse is 1/a rounded to a whole number
Assumes a prime value of a guarantees an inverse modulo n
Confuses the additive inverse n - a with the multiplicative one
Believes a large enough modulus makes inverses exist

A multiplicative inverse of a modulo n does not always exist - for which a does it exist, and why?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

What "inverse modulo n" means

The condition, both directions

What this looks like for concrete moduli

Why a rolling fingerprint depends on it

Where engineers go wrong

▾common follow-ups3 questions

▾analogy~20 s

▾red flags5 flags

What "inverse modulo n" means

The condition, both directions

What this looks like for concrete moduli

Why a rolling fingerprint depends on it

Where engineers go wrong

answer

go deeper