Loading…

mediumMath GeometrySometimes asked

Extended Euclidean Algorithm

Q: How do you solve Extended Euclidean Algorithm using the Brute-Force Search for Coefficients (Baseline) approach?

When to use it: Mention first to show you understand what Bézout coefficients ARE before producing them efficiently — then discard it as exponential. The modular inverse has a definition you can test directly: `a⁻¹` is the value `x` in `[1, m)` with `(a·x) mod m == 1`. The brute-force approach simply tries every `x` in that range and returns the first that satisfies the test. **Why it is correct.** If `gcd(a, m) = 1`, exactly one `x` in `[1, m)` satisfies `a·x ≡ 1 (mod m)`, and the linear scan is guaranteed to find it. If `gcd(a, m) ≠ 1`, no `x` works and the scan finishes empty — correctly reporting 'no inverse'. **Why it does not ship.** The scan is `O(m)`. With `m` up to `10⁹` you'd perform on the order of a billion modular multiplications for a single inverse — far too slow, and it gives no help at all for finding general Bézout coefficients of two large numbers (there's no bounded range to scan there). **The structure we're missing.** Brute force ignores that `a` and `m` carry arithmetic structure: their gcd can be computed in `O(log min(a, m))` steps, and the *same* recursion can hand back the coefficients for free. Recognising that the Euclidean algorithm already does most of the work is the leap to the optimal method. Time complexity: O(m) per inverse / unbounded for general x, y. Space complexity: O(1).

Math & Number Theory · 21 of 36 · 11 min

Given two integers a and b, return a triple (g, x, y) where g = gcd(a, b) and x, y are integers satisfying the Bézout identity:

a·x + b·y = g.

As the headline application, given a and a modulus m with gcd(a, m) = 1, return the modular inverse a⁻¹ mod m — the unique value in [0, m) such that a · a⁻¹ ≡ 1 (mod m).

In plain English

Plain GCD answers 'what is the largest common divisor?'. The extended version also answers 'what integer combination of a and b produces that divisor?'. Bézout's identity guarantees such integers x, y exist whenever g = gcd(a, b). Computing them lets us solve a·x ≡ 1 (mod m): if gcd(a, m) = 1, then a·x + m·y = 1 for some x, y, and reading that modulo m gives a·x ≡ 1, so x is a's inverse.

Examples

Example 1

Input: a = 30, b = 12
Output: (6, 1, -2)
Note: gcd(30, 12) = 6, and 30·1 + 12·(−2) = 30 − 24 = 6.

Example 2

Input: a = 3, m = 11 (modular inverse)
Output: 4
Note: Extended GCD gives 3·4 + 11·(−1) = 1, so 3·4 ≡ 1 (mod 11). The inverse of 3 is 4.

Example 3

Input: a = 6, m = 9 (modular inverse)
Output: no inverse
Note: gcd(6, 9) = 3 ≠ 1, so 6 has no inverse mod 9 — there's no x with 6x ≡ 1 (mod 9).

Constraints

−10⁹ ≤ a, b ≤ 10⁹ (use 64-bit integers in Java for the coefficients)
For the inverse: 1 ≤ a < m, with gcd(a, m) = 1 (otherwise no inverse exists)
1 ≤ m ≤ 10⁹ (m need NOT be prime — that's the point)
Return x, y as integers; the inverse must be normalised to [0, m)

Clarifying questions4First question: Do you want just the gcd, or the coefficients x and y too?Explore questions

Q1.Do you want just the gcd, or the coefficients x and y too?
The coefficients — that's what 'extended' means. If only the gcd were needed, plain Euclid would do.
Q2.Is the modulus m prime?
Not necessarily. If it were prime I could use Fermat (a^(m−2)). Extended GCD is the tool precisely because it works for any m coprime to a.
Q3.What if gcd(a, m) ≠ 1?
Then no modular inverse exists. Extended GCD returns g ≠ 1, which is exactly the signal to report 'no inverse' rather than dividing.
Q4.Can a or b be negative or zero?
Yes. The recursion handles b = 0 as the base case. Negative inputs work too; I normalise the final inverse into [0, m) with ((x % m) + m) % m.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Plain GCD tells you gcd(a, b). The extended version also returns integers x and y with a·x + b·y = gcd(a, b) — the Bézout coefficients. Run the Euclidean recursion, and on the way back up unwind the identity: if (g, x₁, y₁) solves b·x₁ + (a mod b)·y₁ = g, then x = y₁ and y = x₁ − (a / b)·y₁ solves a·x + b·y = g. The headline use is the modular inverse: when gcd(a, m) = 1, x mod m is a⁻¹ mod m, because a·x ≡ 1 (mod m).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can derive the Bézout coefficients by unwinding Euclid's recursion, and whether you know that the modular inverse exists exactly when gcd(a, m) = 1 — including the case where m is not prime.

Where candidates slip

Getting the back-substitution update wrong (forgetting the swap or the quotient term), forgetting to normalise a negative x into [0, m), or assuming an inverse always exists without checking gcd = 1.

How to stand out

State the identity a·x + b·y = gcd(a, b), show the one-line coefficient update from the recursive result, and explain WHY x mod m is the inverse: a·x ≡ 1 (mod m) drops out of a·x + m·y = 1.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute-Force Search for Coefficients (Baseline)	`O(m) per inverse / unbounded for general x, y`	`O(1)`	Mention first to show you understand what Bézout coefficients ARE before producing them efficiently — then discard it as exponential.	Read
2	Extended Euclidean Recursion (Optimal)Optimal	`O(log min(a, b))`	`O(log min(a, b)) recursion`	The answer they want. Phrase it as 'run Euclid, and rebuild the coefficients on the way back with x = y₁, y = x₁ − (a/b)·y₁'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewextgcd(a, b)b == 0 ?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute-Force Search for Coefficients (Baseline)

TimeO(m) per inverse / unbounded for general x, ySpaceO(1)

Mention first to show you understand what Bézout coefficients ARE before producing them efficiently — then discard it as exponential.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

For the modular inverse, the definition is direct: find x in [1, m) with (a·x) mod m == 1. How would you find it without any number theory?

2Hint 2Explore hint

Just try every candidate x from 1 to m − 1 and test a·x mod m == 1. The first hit is the inverse.

3Hint 3Explore hint

This is O(m). For m up to 10⁹ that's a billion multiplications — correct but far too slow. What structure lets us skip the search?

A · Core idea

The modular inverse has a definition you can test directly: a⁻¹ is the value x in [1, m) with (a·x) mod m == 1. The brute-force approach simply tries every x in that range and returns the first that satisfies the test.

Why it is correct. If gcd(a, m) = 1, exactly one x in [1, m) satisfies a·x ≡ 1 (mod m), and the linear scan is guaranteed to find it. If gcd(a, m) ≠ 1, no x works and the scan finishes empty — correctly reporting 'no inverse'.

Why it does not ship. The scan is O(m). With m up to 10⁹ you'd perform on the order of a billion modular multiplications for a single inverse — far too slow, and it gives no help at all for finding general Bézout coefficients of two large numbers (there's no bounded range to scan there).

The structure we're missing. Brute force ignores that a and m carry arithmetic structure: their gcd can be computed in O(log min(a, m)) steps, and the same recursion can hand back the coefficients for free. Recognising that the Euclidean algorithm already does most of the work is the leap to the optimal method.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = 3, m = 11

x=1

3·1 mod 11 = 3

Stateno

Final result4

C · Code with teaching comments

Reference implementation previewpublic long modInverseBruteForce(long a, long m) { a = ((a % m) + m) % m; for (long x = 1; x < m; x++) { if ((a * x) % m == 1) { return x;Explore the full code

solution.javaJava

Brute-Force Search for Coefficients (Baseline) — reference

3 teaching notes

1
public long modInverseBruteForce(long a, long m) {
2
    // Normalise a into [0, m) so the product test behaves even for negative a.
3
    a = ((a % m) + m) % m;
4
    for (long x = 1; x < m; x++) {
5
        // Direct definition of the inverse; a and x are long so a*x won't overflow for
6
        // m up to 10⁹.
7
        if ((a * x) % m == 1) {
8
            return x;
9
        }
10
    }
11
    return -1; // no inverse (gcd(a, m) != 1)
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(m) per inverse / unbounded for general x, y timeO(1) spaceOpen the invariant and proofExplore the proof

Brute force is a useful sanity check for tiny m (verify the fast inverse against it), but it is exponential in the bit-length of m and useless for general coefficients. It exists only to make the speedup of unwinding Euclid concrete.

ComplexityO(m) per inverse / unbounded for general x, y time, O(1) space — Scanning x from 1 to m − 1 and testing a·x mod m == 1 is O(m) time, O(1) space. For the general Bézout coefficients there's no finite range to scan, so brute force doesn't even terminate cleanly — another reason it's only a conceptual baseline.

E · Edge cases and pitfalls3Running it for m ~ 10⁹ — a billion iterations, far too slow.Explore edge cases

Pitfalls

Running it for m ~ 10⁹ — a billion iterations, far too slow.
Assuming it returns something useful for general Bézout coefficients — it only addresses the inverse.
Forgetting the −1 sentinel when no inverse exists.

03.2

Approach 2 of 2 · Optimal

Extended Euclidean Recursion (Optimal)

TimeO(log min(a, b))SpaceO(log min(a, b)) recursion

The answer they want. Phrase it as 'run Euclid, and rebuild the coefficients on the way back with x = y₁, y = x₁ − (a/b)·y₁'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Plain Euclid uses gcd(a, b) = gcd(b, a mod b) until b = 0. Suppose the recursive call already gave you coefficients for the smaller pair (b, a mod b). Can you convert them into coefficients for (a, b)?

2Hint 2Explore hint

At the base case b = 0, gcd is a and a·1 + 0·0 = a, so (g, x, y) = (a, 1, 0). Now propagate upward.

3Hint 3Explore hint

If b·x₁ + (a mod b)·y₁ = g and you substitute a mod b = a − (a/b)·b, collecting terms gives a·y₁ + b·(x₁ − (a/b)·y₁) = g. So the new x is y₁ and the new y is x₁ − (a/b)·y₁.

A · Core idea

Run the Euclidean recursion and, instead of only tracking the gcd, carry the Bézout coefficients back up the call stack. The base case and the one-line update are the whole algorithm.

The base case. When b == 0, the gcd is a, and the identity a·1 + 0·0 = a holds, so return (a, 1, 0). This seeds the coefficients at the bottom of the recursion.

The back-substitution — where the magic is. Suppose the recursive call on (b, a mod b) returned (g, x₁, y₁) satisfying b·x₁ + (a mod b)·y₁ = g. We want x, y with a·x + b·y = g. Substitute the definition a mod b = a − ⌊a/b⌋·b into the recursive identity:

b·x₁ + (a − ⌊a/b⌋·b)·y₁ = g.

Regroup by a and b:

a·y₁ + b·(x₁ − ⌊a/b⌋·y₁) = g.

Matching against a·x + b·y = g reads off the update directly: x = y₁ and y = x₁ − ⌊a/b⌋·y₁. That single swap-and-subtract is the entire 'extended' part. Reverse the swap or drop the quotient term and the identity silently fails to hold.

Why this is fast. The recursion is plain Euclid, so the depth is O(log min(a, b)) — the worst case is consecutive Fibonacci numbers (Lamé's theorem). Each level does one division and a couple of multiplications, all O(1).

From coefficients to a modular inverse. Call extgcd(a, m) to get (g, x, y) with a·x + m·y = g. If g ≠ 1, then a and m share a factor and no inverse exists — report that, don't divide. If g == 1, read the identity modulo m: the m·y term vanishes, leaving a·x ≡ 1 (mod m). So x is the inverse. The raw x may be negative, so normalise it with ((x % m) + m) % m to land in [0, m).

Why overflow-safe. The coefficients and the product ⌊a/b⌋·y₁ can exceed 32 bits for large inputs, so Java uses long throughout. Python integers are arbitrary precision, so there is nothing to guard there.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = 3, m = 11 (compute 3⁻¹ mod 11)

Array state

(1, 0) base

return (1, 1, 0)

level ↓

g=1

[0]

x=1

[1]

y=0

[2]

Current pointerResolved stateNot processed

Final resultg = 1, x = 4 → inverse of 3 mod 11 is 4

C · Code with teaching comments

solution.javaJava

Extended Euclidean Recursion (Optimal) — optimal

6 teaching notes

1
// Returns {g, x, y} with a*x + b*y = g = gcd(a, b).
2
public long[] extgcd(long a, long b) {
3
    if (b == 0) {
4
        return new long[]{a, 1, 0};
5
    }
6
    // Recurse on the smaller pair — this is the plain Euclid step that bounds depth to
7
    // O(log min(a,b)).
8
    long[] r = extgcd(b, a % b);
9
    long g = r[0], x1 = r[1], y1 = r[2];
10
    // New x is the child's y₁ — the swap half of the update.
11
    long x = y1;
12
    // New y subtracts ⌊a/b⌋·y₁; using long keeps (a/b)*y1 from overflowing.
13
    long y = x1 - (a / b) * y1;
14
    return new long[]{g, x, y};
15
}
16
 
17
// Modular inverse of a mod m, or -1 if none (gcd != 1).
18
public long modInverse(long a, long m) {
19
    long[] r = extgcd(((a % m) + m) % m, m);
20
    if (r[0] != 1) return -1;        // no inverse
21
    return ((r[1] % m) + m) % m;     // normalise into [0, m)
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(log min(a, b)) timeO(log min(a, b)) recursion spaceOpen the invariant and proofExplore the proof

The extended algorithm costs essentially nothing on top of plain Euclid — same recursion, two extra arithmetic ops per level — yet it unlocks modular inverses for any modulus coprime to a, including non-prime moduli where Fermat's little theorem doesn't apply. The mental hook: substitute a mod b = a − ⌊a/b⌋·b into the child's identity and regroup; the coefficient update writes itself.

ComplexityO(log min(a, b)) time, O(log min(a, b)) recursion space — Each recursive step replaces (a, b) with (b, a mod b), exactly the Euclidean algorithm, so the depth is O(log min(a, b)) by Lamé's theorem (worst case consecutive Fibonacci numbers). Each level does O(1) arithmetic; recursion stack is O(log min(a, b)).

E · Edge cases and pitfalls9extgcd(a, 0) — Base case returns (a, 1, 0): gcd is a, coefficients trivial.Explore edge cases

Edge cases handled

extgcd(a, 0)Base case returns (a, 1, 0): gcd is a, coefficients trivial.
modInverse(1, m)gcd(1, m) = 1, inverse is 1 (1·1 ≡ 1).
modInverse(6, 9)extgcd returns g = 3 ≠ 1 → return −1, no inverse exists.
modInverse(2, 4)gcd(2, 4) = 2 ≠ 1 → no inverse; even though 2 < 4, it shares a factor.

Pitfalls

Swapping the update wrong — using x = x₁ or dropping the ⌊a/b⌋ term breaks the identity.
Forgetting the base case returns (a, 1, 0), not (a, 0, 1).
Using the raw negative x as an inverse — normalise with ((x % m) + m) % m.
Dividing anyway when g ≠ 1 — there is no inverse; report failure.
Using int in Java — coefficients and (a/b)·y₁ can exceed 32 bits.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Returns {g, x, y} with a*x + b*y = g = gcd(a, b). public long[] extgcd(long a, long b) { if (b == 0) { return new long[]{a, 1, 0}; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong coefficient update on the unwind

The identity only holds for x = y₁, y = x₁ − ⌊a/b⌋·y₁. Forgetting the swap or the quotient term produces coefficients that don't satisfy a·x + b·y = g, so the 'inverse' is silently wrong.

Explore the code comparison

Don't write this

long[] r = extgcd(b, a % b);
long x = r[1];                 // forgot the swap
long y = r[2] - (a / b) * r[1]; // wrong terms
return new long[]{r[0], x, y};

Write this instead

long[] r = extgcd(b, a % b);
long x = r[2];                 // x = y1 (swap)
long y = r[1] - (a / b) * r[2]; // y = x1 - (a/b)*y1
return new long[]{r[0], x, y};

Returning a negative inverse

The Bézout x can be negative (e.g. −7 for some inverse mod 11). A modular inverse must live in [0, m); using the raw value breaks later modular arithmetic.

Explore the code comparison

Don't write this

g, x, _ = self.extgcd(a % m, m)
return x            # may be negative

Write this instead

g, x, _ = self.extgcd(a % m, m)
if g != 1:
    return -1
return (x % m + m) % m   # forced into [0, m)

Assuming the inverse always exists

If gcd(a, m) ≠ 1 there is no x with a·x ≡ 1 (mod m). Skipping the g == 1 check and dividing/returning x gives a meaningless value.

Explore the code comparison

Don't write this

g, x, _ = self.extgcd(a, m)
return (x % m + m) % m   # ignores g != 1 case

Write this instead

g, x, _ = self.extgcd(a, m)
if g != 1:
    return -1            # no inverse — report it
return (x % m + m) % m

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Euclid's recursion plus back-substitution of the Bézout identity a·x + b·y = gcd(a, b)

Code pattern to memorize

extgcd(a, 0) = (a, 1, 0)
extgcd(a, b):
    (g, x1, y1) = extgcd(b, a mod b)
    return (g, y1, x1 - (a / b) * y1)
# modular inverse of a mod m (needs gcd(a, m) == 1):
# inv = ((x % m) + m) % m

Rules to remember

1Base case is b == 0: gcd is a, and a·1 + 0·0 = a, so return (a, 1, 0).
2On the way back, the new coefficients are x = y₁ and y = x₁ − (a / b)·y₁ — swap, then subtract the quotient times the old y. Getting this update backwards is the classic bug.
3A modular inverse exists iff gcd(a, m) == 1. If the returned g ≠ 1, there is no inverse — don't divide.
4The raw x can be negative; normalise with ((x % m) + m) % m before using it as an inverse.
5Use long in Java — intermediate coefficients and products like (a / b) * y₁ can exceed 32 bits. Python integers are unbounded, so no overflow.

Use this pattern when

You need a **modular inverse** a⁻¹ mod m when m is **not** prime (so Fermat's little theorem doesn't apply)
Solving a linear Diophantine equation a·x + b·y = c for integer x, y
The Chinese Remainder Theorem's constructive step needs inverses of moduli
Any time you want gcd AND the coefficients that produce it, not just the gcd

Choose another pattern when

m is prime and you want a⁻¹ mod m → Fermat (a^(m−2) mod m) is shorter to write
You only need gcd(a, b), not the coefficients → plain Euclid
gcd(a, m) ≠ 1 → no inverse exists; extended GCD will tell you, but you can't proceed
You need a^k mod m, not an inverse → fast modular exponentiation

Interview takeaway

Extended Euclid is plain Euclid that remembers how to rebuild the gcd from a and b. The back-substitution x = y₁, y = x₁ − (a/b)·y₁ is the only line to memorise. Its payoff is the modular inverse for any modulus coprime to a — the one tool that works when m isn't prime and Fermat is off the table. It also underpins CRT and linear Diophantine solving.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternBézout coefficients via Euclid's recursion. Reach for it whenever you need a modular inverse for a modulus that is NOT prime, or to solve a·x + b·y = c over the integers. It is the engine behind CRT reconstruction and any 'invert modulo composite' step.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Collatz Sequence Length

Continue · Next problem

Factorial of a Number

mediumMath GeometrySometimes asked

Extended Euclidean Algorithm

Math & Number Theory · 21 of 36 · 11 min

Given two integers a and b, return a triple (g, x, y) where g = gcd(a, b) and x, y are integers satisfying the Bézout identity:

a·x + b·y = g.

As the headline application, given a and a modulus m with gcd(a, m) = 1, return the modular inverse a⁻¹ mod m — the unique value in [0, m) such that a · a⁻¹ ≡ 1 (mod m).

In plain English

Examples

Example 1

Input: a = 30, b = 12
Output: (6, 1, -2)
Note: gcd(30, 12) = 6, and 30·1 + 12·(−2) = 30 − 24 = 6.

Example 2

Input: a = 3, m = 11 (modular inverse)
Output: 4
Note: Extended GCD gives 3·4 + 11·(−1) = 1, so 3·4 ≡ 1 (mod 11). The inverse of 3 is 4.

Example 3

Input: a = 6, m = 9 (modular inverse)
Output: no inverse
Note: gcd(6, 9) = 3 ≠ 1, so 6 has no inverse mod 9 — there's no x with 6x ≡ 1 (mod 9).

Constraints

−10⁹ ≤ a, b ≤ 10⁹ (use 64-bit integers in Java for the coefficients)
For the inverse: 1 ≤ a < m, with gcd(a, m) = 1 (otherwise no inverse exists)
1 ≤ m ≤ 10⁹ (m need NOT be prime — that's the point)
Return x, y as integers; the inverse must be normalised to [0, m)

Clarifying questions4First question: Do you want just the gcd, or the coefficients x and y too?Explore questions

Q1.Do you want just the gcd, or the coefficients x and y too?
The coefficients — that's what 'extended' means. If only the gcd were needed, plain Euclid would do.
Q2.Is the modulus m prime?
Not necessarily. If it were prime I could use Fermat (a^(m−2)). Extended GCD is the tool precisely because it works for any m coprime to a.
Q3.What if gcd(a, m) ≠ 1?
Then no modular inverse exists. Extended GCD returns g ≠ 1, which is exactly the signal to report 'no inverse' rather than dividing.
Q4.Can a or b be negative or zero?
Yes. The recursion handles b = 0 as the base case. Negative inputs work too; I normalise the final inverse into [0, m) with ((x % m) + m) % m.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Getting the back-substitution update wrong (forgetting the swap or the quotient term), forgetting to normalise a negative x into [0, m), or assuming an inverse always exists without checking gcd = 1.

How to stand out

State the identity a·x + b·y = gcd(a, b), show the one-line coefficient update from the recursive result, and explain WHY x mod m is the inverse: a·x ≡ 1 (mod m) drops out of a·x + m·y = 1.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute-Force Search for Coefficients (Baseline)	`O(m) per inverse / unbounded for general x, y`	`O(1)`	Mention first to show you understand what Bézout coefficients ARE before producing them efficiently — then discard it as exponential.	Read
2	Extended Euclidean Recursion (Optimal)Optimal	`O(log min(a, b))`	`O(log min(a, b)) recursion`	The answer they want. Phrase it as 'run Euclid, and rebuild the coefficients on the way back with x = y₁, y = x₁ − (a/b)·y₁'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute-Force Search for Coefficients (Baseline)

TimeO(m) per inverse / unbounded for general x, ySpaceO(1)

Mention first to show you understand what Bézout coefficients ARE before producing them efficiently — then discard it as exponential.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

For the modular inverse, the definition is direct: find x in [1, m) with (a·x) mod m == 1. How would you find it without any number theory?

2Hint 2Explore hint

Just try every candidate x from 1 to m − 1 and test a·x mod m == 1. The first hit is the inverse.

3Hint 3Explore hint

This is O(m). For m up to 10⁹ that's a billion multiplications — correct but far too slow. What structure lets us skip the search?

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = 3, m = 11

x=1

3·1 mod 11 = 3

Stateno

Final result4

C · Code with teaching comments

Reference implementation previewpublic long modInverseBruteForce(long a, long m) { a = ((a % m) + m) % m; for (long x = 1; x < m; x++) { if ((a * x) % m == 1) { return x;Explore the full code

solution.javaJava

Brute-Force Search for Coefficients (Baseline) — reference

3 teaching notes

1
public long modInverseBruteForce(long a, long m) {
2
    // Normalise a into [0, m) so the product test behaves even for negative a.
3
    a = ((a % m) + m) % m;
4
    for (long x = 1; x < m; x++) {
5
        // Direct definition of the inverse; a and x are long so a*x won't overflow for
6
        // m up to 10⁹.
7
        if ((a * x) % m == 1) {
8
            return x;
9
        }
10
    }
11
    return -1; // no inverse (gcd(a, m) != 1)
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(m) per inverse / unbounded for general x, y timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Running it for m ~ 10⁹ — a billion iterations, far too slow.Explore edge cases

Pitfalls

Running it for m ~ 10⁹ — a billion iterations, far too slow.
Assuming it returns something useful for general Bézout coefficients — it only addresses the inverse.
Forgetting the −1 sentinel when no inverse exists.

03.2

Approach 2 of 2 · Optimal

Extended Euclidean Recursion (Optimal)

TimeO(log min(a, b))SpaceO(log min(a, b)) recursion

The answer they want. Phrase it as 'run Euclid, and rebuild the coefficients on the way back with x = y₁, y = x₁ − (a/b)·y₁'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

2Hint 2Explore hint

At the base case b = 0, gcd is a and a·1 + 0·0 = a, so (g, x, y) = (a, 1, 0). Now propagate upward.

3Hint 3Explore hint

A · Core idea

Run the Euclidean recursion and, instead of only tracking the gcd, carry the Bézout coefficients back up the call stack. The base case and the one-line update are the whole algorithm.

The base case. When b == 0, the gcd is a, and the identity a·1 + 0·0 = a holds, so return (a, 1, 0). This seeds the coefficients at the bottom of the recursion.

b·x₁ + (a − ⌊a/b⌋·b)·y₁ = g.

Regroup by a and b:

a·y₁ + b·(x₁ − ⌊a/b⌋·y₁) = g.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = 3, m = 11 (compute 3⁻¹ mod 11)

Array state

(1, 0) base

return (1, 1, 0)

level ↓

g=1

[0]

x=1

[1]

y=0

[2]

Current pointerResolved stateNot processed

Final resultg = 1, x = 4 → inverse of 3 mod 11 is 4

C · Code with teaching comments

solution.javaJava

Extended Euclidean Recursion (Optimal) — optimal

6 teaching notes

1
// Returns {g, x, y} with a*x + b*y = g = gcd(a, b).
2
public long[] extgcd(long a, long b) {
3
    if (b == 0) {
4
        return new long[]{a, 1, 0};
5
    }
6
    // Recurse on the smaller pair — this is the plain Euclid step that bounds depth to
7
    // O(log min(a,b)).
8
    long[] r = extgcd(b, a % b);
9
    long g = r[0], x1 = r[1], y1 = r[2];
10
    // New x is the child's y₁ — the swap half of the update.
11
    long x = y1;
12
    // New y subtracts ⌊a/b⌋·y₁; using long keeps (a/b)*y1 from overflowing.
13
    long y = x1 - (a / b) * y1;
14
    return new long[]{g, x, y};
15
}
16
 
17
// Modular inverse of a mod m, or -1 if none (gcd != 1).
18
public long modInverse(long a, long m) {
19
    long[] r = extgcd(((a % m) + m) % m, m);
20
    if (r[0] != 1) return -1;        // no inverse
21
    return ((r[1] % m) + m) % m;     // normalise into [0, m)
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(log min(a, b)) timeO(log min(a, b)) recursion spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls9extgcd(a, 0) — Base case returns (a, 1, 0): gcd is a, coefficients trivial.Explore edge cases

Edge cases handled

extgcd(a, 0)Base case returns (a, 1, 0): gcd is a, coefficients trivial.
modInverse(1, m)gcd(1, m) = 1, inverse is 1 (1·1 ≡ 1).
modInverse(6, 9)extgcd returns g = 3 ≠ 1 → return −1, no inverse exists.
modInverse(2, 4)gcd(2, 4) = 2 ≠ 1 → no inverse; even though 2 < 4, it shares a factor.

Pitfalls

Swapping the update wrong — using x = x₁ or dropping the ⌊a/b⌋ term breaks the identity.
Forgetting the base case returns (a, 1, 0), not (a, 0, 1).
Using the raw negative x as an inverse — normalise with ((x % m) + m) % m.
Dividing anyway when g ≠ 1 — there is no inverse; report failure.
Using int in Java — coefficients and (a/b)·y₁ can exceed 32 bits.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Returns {g, x, y} with a*x + b*y = g = gcd(a, b). public long[] extgcd(long a, long b) { if (b == 0) { return new long[]{a, 1, 0}; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong coefficient update on the unwind

Explore the code comparison

Don't write this

long[] r = extgcd(b, a % b);
long x = r[1];                 // forgot the swap
long y = r[2] - (a / b) * r[1]; // wrong terms
return new long[]{r[0], x, y};

Write this instead

long[] r = extgcd(b, a % b);
long x = r[2];                 // x = y1 (swap)
long y = r[1] - (a / b) * r[2]; // y = x1 - (a/b)*y1
return new long[]{r[0], x, y};

Returning a negative inverse

The Bézout x can be negative (e.g. −7 for some inverse mod 11). A modular inverse must live in [0, m); using the raw value breaks later modular arithmetic.

Explore the code comparison

Don't write this

g, x, _ = self.extgcd(a % m, m)
return x            # may be negative

Write this instead

g, x, _ = self.extgcd(a % m, m)
if g != 1:
    return -1
return (x % m + m) % m   # forced into [0, m)

Assuming the inverse always exists

If gcd(a, m) ≠ 1 there is no x with a·x ≡ 1 (mod m). Skipping the g == 1 check and dividing/returning x gives a meaningless value.

Explore the code comparison

Don't write this

g, x, _ = self.extgcd(a, m)
return (x % m + m) % m   # ignores g != 1 case

Write this instead

g, x, _ = self.extgcd(a, m)
if g != 1:
    return -1            # no inverse — report it
return (x % m + m) % m

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Euclid's recursion plus back-substitution of the Bézout identity a·x + b·y = gcd(a, b)

Code pattern to memorize

extgcd(a, 0) = (a, 1, 0)
extgcd(a, b):
    (g, x1, y1) = extgcd(b, a mod b)
    return (g, y1, x1 - (a / b) * y1)
# modular inverse of a mod m (needs gcd(a, m) == 1):
# inv = ((x % m) + m) % m

Rules to remember

1Base case is b == 0: gcd is a, and a·1 + 0·0 = a, so return (a, 1, 0).
2On the way back, the new coefficients are x = y₁ and y = x₁ − (a / b)·y₁ — swap, then subtract the quotient times the old y. Getting this update backwards is the classic bug.
3A modular inverse exists iff gcd(a, m) == 1. If the returned g ≠ 1, there is no inverse — don't divide.
4The raw x can be negative; normalise with ((x % m) + m) % m before using it as an inverse.
5Use long in Java — intermediate coefficients and products like (a / b) * y₁ can exceed 32 bits. Python integers are unbounded, so no overflow.

Use this pattern when

You need a **modular inverse** a⁻¹ mod m when m is **not** prime (so Fermat's little theorem doesn't apply)
Solving a linear Diophantine equation a·x + b·y = c for integer x, y
The Chinese Remainder Theorem's constructive step needs inverses of moduli
Any time you want gcd AND the coefficients that produce it, not just the gcd

Choose another pattern when

m is prime and you want a⁻¹ mod m → Fermat (a^(m−2) mod m) is shorter to write
You only need gcd(a, b), not the coefficients → plain Euclid
gcd(a, m) ≠ 1 → no inverse exists; extended GCD will tell you, but you can't proceed
You need a^k mod m, not an inverse → fast modular exponentiation

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Collatz Sequence Length

Continue · Next problem

Factorial of a Number