Extended Euclidean Algorithm: Algorithm Implementation and Proof

1. Introduction and Core Concepts

The Extended Euclidean Algorithm is a fundamental extension of the classic Euclidean Algorithm that does far more than simply compute the greatest common divisor (GCD) of two integers. While Euclid's original algorithm efficiently finds gcd(a, b), the extended version also finds integer coefficients x and y such that ax + by = gcd(a, b). This linear combination, known as Bézout's identity, is the cornerstone of many areas in modern mathematics and computer science.

At its heart, the extended euclidean algorithm answers a deceptively simple question: given two integers a and b, can we express their greatest common divisor as an integer linear combination of a and b? Bézout's theorem guarantees that such coefficients always exist, and the extended algorithm provides a constructive, efficient method to find them. For example, for a = 240 and b = 46, we have gcd(240, 46) = 2, and the algorithm finds x = -9 and y = 47 because 240 × (-9) + 46 × 47 = -2160 + 2162 = 2.

Understanding why this matters requires appreciating the role of the GCD in number theory. The GCD represents the largest integer that divides both numbers without remainder, and it encodes deep structural information about their relationship. When gcd(a, b) = 1, we say a and b are coprime, a condition that is essential for modular inverses, cryptographic key generation, and solving linear Diophantine equations. The extended euclidean algorithm transforms the GCD from a mere numeric value into a powerful computational tool that reveals the underlying linear structure.

This algorithm is particularly celebrated for its elegance and efficiency. Like its predecessor, it relies solely on integer division and remainders, requires no factorization, and runs in logarithmic time. Its importance extends far beyond theoretical mathematics into practical domains including RSA cryptography, error-correcting codes, and the solution of congruences. Any computer science student or software engineer working with modular arithmetic, cryptography, or competitive programming will inevitably encounter and depend on this algorithm.

What is Bézout's Identity?

Bézout's identity states that for any integers a and b with gcd(a, b) = d, there exist integers x and y such that ax + by = d. Furthermore, d is the smallest positive integer that can be expressed in this form. The pair (x, y) is not unique; if (x, y) is one solution, then (x + k × (b/d), y - k × (a/d)) is also a solution for any integer k. The extended euclidean algorithm finds one particular pair, often called the Bézout coefficients, which can then be used to generate all other solutions.

Core Definitions and Prerequisites

To fully grasp the extended euclidean algorithm, you should be comfortable with integer division with remainder (the Division Algorithm), modular arithmetic, and the concept of the greatest common divisor. The algorithm operates on non-negative integers, though it can be easily adapted for negative inputs. The key insight is that the GCD is preserved under the operation gcd(a, b) = gcd(b, a mod b), and the linear combination can be propagated backward through the same sequence of remainders.

2. How It Works

The extended euclidean algorithm works by augmenting the standard Euclidean Algorithm with additional bookkeeping to track how each remainder can be expressed as a linear combination of the original inputs a and b. The standard algorithm generates a sequence of remainders: r0 = a, r1 = b, r2 = a mod b, r3 = b mod r2, and so on until rk = 0. The last non-zero remainder rk-1 is the GCD. The extended version maintains for each remainder ri two coefficients xi and yi such that ri = a × xi + b × yi.

We initialize the sequences with r0 = a = a × 1 + b × 0, so (x0, y0) = (1, 0), and r1 = b = a × 0 + b × 1, so (x1, y1) = (0, 1). For each subsequent step, we compute the quotient qi = ri-1 // ri (integer division). The next remainder is ri+1 = ri-1 - qi × ri. Crucially, the coefficients obey the exact same recurrence: xi+1 = xi-1 - qi × xi and yi+1 = yi-1 - qi × yi. This parallel update ensures the invariant ri = a × xi + b × yi holds at every step.

When the algorithm terminates with rk = 0, we have rk-1 = gcd(a, b) = a × xk-1 + b × yk-1, giving us the desired coefficients. This iterative formulation is efficient and naturally translates to code. There is also an equivalent recursive formulation that is often more intuitive for understanding the proof of correctness. The recursive view expresses the solution for (a, b) in terms of the solution for (b, a mod b).

The mathematical justification hinges on the fact that if we know x' and y' such that b × x' + (a mod b) × y' = gcd(a, b), we can rewrite a mod b as a - floor(a / b) × b. Substituting yields gcd(a, b) = b × x' + (a - floor(a / b) × b) × y' = a × y' + b × (x' - floor(a / b) × y'). Thus, for the original pair (a, b), the coefficients are x = y' and y = x' - floor(a / b) × y'. This backward substitution is exactly what the iterative coefficient updates accomplish.

The Invariant Principle

The correctness of the algorithm rests on maintaining a loop invariant. At every iteration i, the current remainders and coefficients satisfy ri = a × xi + b × yi and ri+1 = a × xi+1 + b × yi+1. Since the remainders strictly decrease and remain non-negative, the sequence must terminate. The invariant, combined with the termination condition rk = 0, guarantees that rk-1 is both the GCD and the correct linear combination. This invariant-based reasoning is a classic example of program verification in algorithm design.

Recursive vs. Iterative Perspective

Conceptually, the recursive approach works backwards: it recurses down to the base case gcd(d, 0) = d = d × 1 + 0 × 0, then unwinds the recursion, transforming coefficients at each level using the formula above. The iterative approach works forwards, updating coefficients alongside remainders without needing a call stack. Both are mathematically equivalent and have the same time complexity, but the iterative version is generally preferred in production code to avoid recursion depth limits for very large integers.

3. Implementation

Implementing the extended euclidean algorithm is straightforward in any language that supports integer arithmetic. Below are several Python implementations illustrating different styles, from the classic recursive version to an iterative version and a version that directly computes the modular inverse.

The most important implementation detail is handling the base case correctly and ensuring integer division is used. Python's // operator performs floor division, which works correctly for non-negative inputs. For negative inputs, it is best to take absolute values and then adjust the signs of the coefficients at the end. Care must also be taken to handle the case where one of the inputs is zero.

def extended_gcd_recursive(a, b):
    """
    Recursive Extended Euclidean Algorithm.
    Returns (gcd, x, y) such that a*x + b*y == gcd(a, b)
    """
    # Base case: if b is 0, gcd is a and coefficients are (1, 0)
    if b == 0:
        return (a, 1, 0)
    
    # Recursive call for (b, a mod b)
    gcd, x1, y1 = extended_gcd_recursive(b, a % b)
    
    # Update coefficients using the recursive formula
    # x = y1
    # y = x1 - (a // b) * y1
    x = y1
    y = x1 - (a // b) * y1
    
    return (gcd, x, y)

# Example usage
g, x, y = extended_gcd_recursive(240, 46)
print(f"gcd= {g}, x= {x}, y= {y}")  # gcd=2, x=-9, y=47
print(f"Verification: 240*{x} + 46*{y} = {240*x + 46*y}")
# Check that a*x + b*y == gcd
assert 240 * x + 46 * y == g

def extended_gcd_iterative(a, b):
    """
    Iterative Extended Euclidean Algorithm.
    More efficient and avoids recursion limits.
    Returns (gcd, x, y) such that a*x + b*y == gcd
    """
    # Initialize coefficients for r0 = a and r1 = b
    # r0 = a*1 + b*0, r1 = a*0 + b*1
    old_r, r = a, b
    old_s, s = 1, 0  # coefficients for a
    old_t, t = 0, 1  # coefficients for b
    
    # Loop until remainder becomes 0
    while r != 0:
        quotient = old_r // r
        
        # Update remainders: (old_r, r) = (r, old_r - quotient * r)
        old_r, r = r, old_r - quotient * r
        
        # Update coefficients for a and b using same quotient
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t
    
    # old_r is gcd, old_s and old_t are Bezout coefficients
    return (old_r, old_s, old_t)

# Example: iterative version handles large numbers efficiently
g, x, y = extended_gcd_iterative(240, 46)
print(f"gcd={g}, x={x}, y={y}")

# Works for coprime numbers as well
g2, x2, y2 = extended_gcd_iterative(35, 15)
print(f"gcd(35,15)={g2}, x={x2}, y={y2}")  # gcd=5, 35*1 + 15*(-2)=5

def mod_inverse(a, m):
    """
    Compute modular inverse of a modulo m using Extended Euclidean Algorithm.
    Returns x such that (a * x) % m == 1, if it exists.
    Requires gcd(a, m) == 1 (a and m must be coprime).
    """
    gcd, x, y = extended_gcd_iterative(a, m)
    
    # Inverse exists only if a and m are coprime
    if gcd != 1:
        raise ValueError(f"Modular inverse does not exist: gcd({a}, {m}) = {gcd} != 1")
    
    # Ensure result is positive modulo m
    # x may be negative, so we normalize it
    return x % m

# Example: find inverse of 17 mod 43
# 17 * x ≡ 1 (mod 43)
inv = mod_inverse(17, 43)
print(f"Inverse of 17 mod 43 is {inv}")  # 38, since 17*38=646=15*43+1
print(f"Verification: (17 * {inv}) % 43 = {(17 * inv) % 43}")

# Another example: 3 mod 11 -> inverse is 4 because 3*4=12≡1 mod 11
print(f"Inverse of 3 mod 11 is {mod_inverse(3, 11)}")

# This will raise an error because gcd(6, 9) != 1
# print(mod_inverse(6, 9))

def extended_gcd_binary(a, b):
    """
    Extended Euclidean Algorithm with handling for negative inputs
    and comprehensive validation. Returns (gcd, x, y).
    """
    # Handle negative inputs by tracking signs
    sign_a = -1 if a < 0 else 1
    sign_b = -1 if b < 0 else 1
    a_abs, b_abs = abs(a), abs(b)
    
    if a_abs == 0 and b_abs == 0:
        raise ValueError("gcd(0, 0) is undefined")
    if b_abs == 0:
        return (a_abs, sign_a, 0)
    
    # Iterative algorithm on absolute values
    old_r, r = a_abs, b_abs
    old_s, s = 1, 0
    old_t, t = 0, 1
    
    while r != 0:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
        old_t, t = t, old_t - q * t
    
    # Adjust signs of coefficients
    return (old_r, old_s * sign_a, old_t * sign_b)

# Test with negative numbers
g, x, y = extended_gcd_binary(-240, 46)
print(f"gcd(-240,46)={g}, x={x}, y={y}")
print(f"Verification: -240*{x} + 46*{y} = {-240*x + 46*y}")

# Edge case: one zero
g, x, y = extended_gcd_binary(0, 5)
print(f"gcd(0,5)={g}, x={x}, y={y}")  # gcd=5, 0*x + 5*1=5

These implementations demonstrate the core logic while also addressing practical concerns such as sign handling, modular normalization, and error checking. The iterative version is the workhorse for most applications due to its constant space overhead and lack of recursion.

4. Step-by-Step Example

To solidify understanding, let us walk through a complete execution of the extended euclidean algorithm for a = 120 and b = 23. We will trace both the remainders and the Bézout coefficients at each step, verifying the invariant at every stage. This example is small enough to follow by hand but complex enough to illustrate all phases of the algorithm.

We initialize with r0 = 120, r1 = 23, and coefficients (x0, y0) = (1, 0) meaning 120 = 120×1 + 23×0, and (x1, y1) = (0, 1) meaning 23 = 120×0 + 23×1. The algorithm proceeds by repeatedly dividing the previous remainder by the current remainder.

Step 1: Divide 120 by 23. The quotient q1 = 120 // 23 = 5 with remainder r2 = 120 - 5×23 = 120 - 115 = 5. We compute the new coefficients: x2 = x0 - q1×x1 = 1 - 5×0 = 1, and y2 = y0 - q1×y1 = 0 - 5×1 = -5. Check: 120×1 + 23×(-5) = 120 - 115 = 5 = r2. The invariant holds.

Step 2: Divide 23 by 5. Quotient q2 = 23 // 5 = 4, remainder r3 = 23 - 4×5 = 3. Coefficients: x3 = x1 - q2×x2 = 0 - 4×1 = -4, y3 = y1 - q2×y2 = 1 - 4×(-5) = 1 + 20 = 21. Check: 120×(-4) + 23×21 = -480 + 483 = 3 = r3.

Step 3: Divide 5 by 3. Quotient q3 = 5 // 3 = 1, remainder r4 = 5 - 1×3 = 2. Coefficients: x4 = x2 - q3×x3 = 1 - 1×(-4) = 5, y4 = y2 - q3×y3 = -5 - 1×21 = -26. Check: 120×5 + 23×(-26) = 600 - 598 = 2 = r4.

Step 4: Divide 3 by 2. Quotient q4 = 3 // 2 = 1, remainder r5 = 3 - 1×2 = 1. Coefficients: x5 = x3 - q4×x4 = -4 - 1×5 = -9, y5 = y3 - q4×y4 = 21 - 1×(-26) = 47. Check: 120×(-9) + 23×47 = -1080 + 1081 = 1 = r5.

Step 5: Divide 2 by 1. Quotient q5 = 2 // 1 = 2, remainder r6 = 2 - 2×1 = 0. The algorithm terminates because the remainder is zero. The last non-zero remainder is r5 = 1, which is gcd(120, 23). The corresponding coefficients are x5 = -9 and y5 = 47. Thus, we have found that 120×(-9) + 23×47 = 1, confirming Bézout's identity for this coprime pair.

This trace can be summarized in a table that is often used when executing the algorithm by hand. Each row shows the quotient, remainder, and coefficients, making it easy to verify correctness.

Notice how the coefficients grow in magnitude while alternating in sign, yet the linear combination always yields the current remainder. This example also demonstrates that the modular inverse of 120 modulo 23 is -9 mod 23 = 14, because 120×14 = 1680 = 73×23 + 1. Similarly, the inverse of 23 modulo 120 is 47, since 23×47 = 1081 = 9×120 + 1.

5. Complexity Analysis

The extended euclidean algorithm inherits the remarkable efficiency of the Euclidean Algorithm. Its time complexity is logarithmic in the size of the inputs, making it one of the fastest number-theoretic algorithms and suitable for use with very large integers such as those found in cryptography (e.g., 2048-bit numbers).

The key to analyzing its complexity is Lamé's theorem, which states that the number of division steps required to compute gcd(a, b) is at most 5 times the number of decimal digits in min(a, b), and more precisely, is O(log min(a, b)). The worst case occurs when the inputs are consecutive Fibonacci numbers, because Fibonacci numbers produce the smallest possible remainders and thus the longest chain of divisions (each quotient is 1).

Each division step involves arithmetic on integers whose size decreases over time. If we count each division and coefficient update as O(1) for fixed-width integers (e.g., 32-bit or 64-bit), the total time is O(log min(a, b)). For arbitrary-precision integers with n bits, each division costs O(n²) with naive algorithms or O(n log n) with faster methods, leading to an overall complexity of O(n²) or O(n log² n) in bit complexity. However, for most practical purposes and interview analysis, we state the complexity in terms of the number of arithmetic operations.

Space complexity is equally efficient. The iterative version uses only a constant number of integer variables (old_r, r, old_s, s, old_t, t, quotient), so its auxiliary space is O(1). The recursive version uses O(log min(a, b)) stack space due to recursion depth, which is still very modest. No additional data structures are needed.

In practice, the algorithm is extremely fast. Computing the GCD and Bézout coefficients for two 1024-bit integers (about 300 decimal digits) typically takes only a few thousand elementary operations, well under a millisecond on modern hardware. This efficiency is why it is the method of choice for modular inversion in cryptographic libraries, where it may be called thousands of times per second during TLS handshakes or blockchain verification.

Best, Average, and Worst Cases Explained

The best case occurs when b divides a evenly (a mod b == 0), requiring only a single division. The average case, for random integers, is about 12% fewer steps than the worst case and behaves logarithmically. The worst case, as noted, involves consecutive Fibonacci numbers like (Fₙ₊₁, Fₙ), where every quotient is 1 and the number of steps is maximal. Even in this worst case, the logarithmic bound ensures scalability.

6. Variations and Optimizations

While the classic extended euclidean algorithm is already highly efficient, several variations and optimizations have been developed for specific contexts, including performance improvements, handling of special inputs, and adaptation to different algebraic structures.

The Binary Extended Euclidean Algorithm, also known as the Binary GCD extension, replaces division with bit shifts and subtractions, which are cheaper on hardware without fast division units. It is based on the observations that gcd(a, b) = 2 × gcd(a/2, b/2) if both are even, gcd(a, b) = gcd(a/2, b) if only a is even, and gcd(a, b) = gcd((a-b)/2, b) if both are odd. While it reduces the cost of each step, it typically requires more steps overall, but can be faster for very large integers or in hardware implementations.

Another important optimization is the use of Lehmer's GCD technique, which uses the leading digits of large integers to predict quotients without performing full-precision divisions. For numbers with thousands of bits, most quotients can be determined from just the top 1-2 machine words, dramatically reducing the cost of big-integer division. Modern libraries like GMP (GNU Multiple Precision Arithmetic Library) use Lehmer's method and its generalizations to accelerate the extended algorithm for cryptographic-sized integers.

For computing only the modular inverse (rather than both Bézout coefficients), a truncated version can be used that tracks only one coefficient sequence (the one corresponding to a), since y is not needed for the inverse. This halves the number of coefficient updates and slightly improves speed and memory usage. This optimization is common in cryptographic code where only a⁻¹ mod m is required.

The algorithm also generalizes beyond integers. The Extended Euclidean Algorithm works in any Euclidean domain, including polynomials over a field, Gaussian integers, and other principal ideal domains. The polynomial version is crucial for error-correcting codes like Reed-Solomon, where it is used to find the error locator polynomial. The structure remains identical: replace integer division with polynomial division and absolute value with degree.

Iterative vs. Recursive Trade-offs

In languages like Python, recursion depth is limited (default ~1000), so the recursive version can fail for worst-case Fibonacci inputs that are large enough to exceed this depth, even though the numbers themselves fit in memory. The iterative version avoids this entirely and is generally 10-20% faster due to eliminating function call overhead. For educational purposes, the recursive version is clearer, but for production code, the iterative version is strongly preferred.

Extended Binary GCD Pseudocode Concept

The binary variant is particularly useful in embedded systems and smart cards where division is expensive. It maintains coefficients while repeatedly halving even numbers and subtracting, ensuring all intermediate values remain integers. Although more complex to implement correctly with coefficient tracking, it offers constant-time variants that are resistant to side-channel attacks, an important consideration in cryptography.

7. Real-World Applications

The extended euclidean algorithm is not merely an academic curiosity; it is a workhorse behind many of the systems that power the modern digital world. Its ability to compute modular inverses and solve linear Diophantine equations makes it indispensable in cryptography, computer algebra, and distributed systems.

The most prominent application is in RSA cryptography, one of the most widely used public-key cryptosystems. RSA key generation requires finding an integer e (the public exponent) that is coprime to φ(n) = (p-1)(q-1), where p and q are large primes, and then computing d, the modular inverse of e modulo φ(n), such that e×d ≡ 1 mod φ(n). This d is the private exponent. The extended euclidean algorithm is the standard method for computing d efficiently, even when φ(n) is a 2048-bit or 4096-bit number. Without it, RSA would be impractical.

Beyond RSA, the algorithm is central to elliptic curve cryptography (ECC), Diffie-Hellman key exchange, and the Digital Signature Algorithm (DSA), all of which rely heavily on modular inverses for point operations and signature generation. In each TLS handshake that secures your web browsing, the extended algorithm may be invoked multiple times to perform these modular arithmetic operations.

In computer science more broadly, the algorithm is used to solve linear congruences of the form ax ≡ b mod m, which arise in scheduling, hashing, and pseudorandom number generation. It is also used to compute fractions in modular arithmetic, to implement the Chinese Remainder Theorem (CRT) for speeding up RSA decryption and for parallelizing computations, and to find solutions to linear Diophantine equations in areas like resource allocation and integer programming.

Even in seemingly unrelated fields, the algorithm appears. In music theory, it is used to generate Euclidean rhythms. In computer graphics, it helps solve line-drawing problems involving integer grids. Its presence in standard libraries (Python's pow(a, -1, mod) in Python 3.8+ is implemented using the extended algorithm) means that countless developers use it indirectly without even realizing it.

Chinese Remainder Theorem in Practice

Web servers handling thousands of RSA decryptions per second use the Chinese Remainder Theorem to speed up private key operations. Instead of computing m = cᵈ mod n directly with a huge exponent, they compute m₁ = cᵈ mod p and m₂ = cᵈ mod q separately and then combine them using coefficients derived from the extended euclidean algorithm (specifically, the inverse of p modulo q). This optimization, known as CRT-RSA, is a direct and high-impact application of the algorithm in production infrastructure.

8. Comparison with Alternatives

While the extended euclidean algorithm is the most famous method for computing Bézout coefficients and modular inverses, it is not the only approach. Understanding its alternatives helps in choosing the right tool for a given constraint, whether that constraint is code simplicity, constant-time execution, or handling of non-coprime inputs.

The most common alternative for modular inversion is Fermat's Little Theorem, which states that if p is prime and a is not divisible by p, then a^(p-1) ≡ 1 mod p, so a⁻¹ ≡ a^(p-2) mod p. This allows computing the inverse via modular exponentiation (using fast exponentiation by squaring). This method is simple to implement if you already have a modular exponentiation routine and is naturally constant-time, but it only works when the modulus is prime and is generally slower than the extended algorithm for large numbers, requiring O(log p) multiplications.

Another approach is Euler's theorem, a generalization of Fermat's theorem for any modulus m: if gcd(a, m) = 1, then a^φ(m) ≡ 1 mod m, so a⁻¹ ≡ a^(φ(m)-1) mod m. This requires knowing or computing Euler's totient φ(m), which itself requires factorization of m — an expensive operation for large m. Thus, it is rarely used for inversion unless φ(m) is already known.

Brute-force search (testing x = 1, 2, 3, ... until a×x mod m == 1) is conceptually simple but has exponential time complexity O(m) and is completely infeasible for cryptographic sizes. It is only suitable for tiny moduli in educational settings. Finally, the Binary Extended GCD, as discussed, is a variant rather than a true alternative, trading divisions for shifts.

For most software engineering tasks, the extended euclidean algorithm remains the best choice due to its generality, speed, and ability to detect non-invertibility (when gcd != 1). However, in cryptographic implementations that must be resistant to timing attacks, Fermat's method with constant-time exponentiation is sometimes preferred despite being slower, because the extended algorithm's variable number of steps can leak information about the inputs through timing side channels. Modern constant-time extended GCD variants exist to address this.

9. Common Mistakes and Best Practices

Despite its apparent simplicity, implementing the extended euclidean algorithm correctly requires attention to several subtle pitfalls that frequently trap beginners and even experienced developers. Avoiding these mistakes is crucial for correctness, especially in security-sensitive contexts.

A very common mistake is mishandling negative numbers and the sign of the result. The mathematical definition of gcd is typically for non-negative integers, and Bézout coefficients for negative inputs must be adjusted. If you take absolute values for the computation, you must remember to flip the sign of the corresponding coefficient if the original input was negative. Failing to do so yields a linear combination that does not equal the GCD of the original signed inputs. Another frequent error is forgetting to normalize the modular inverse to be positive. The algorithm may return a negative x, but the canonical modular inverse is expected to be in the range [0, m-1], so you must return x % m.

Another pitfall is incorrect handling of edge cases, particularly when one or both inputs are zero. Mathematically, gcd(a, 0) = |a| and gcd(0, 0) is undefined (or sometimes defined as 0). Code that does not explicitly check for b == 0 before performing a % b will raise a division-by-zero error. Similarly, not checking whether gcd(a, m) == 1 before returning a modular inverse can lead to returning a value that does not actually satisfy a×x ≡ 1 mod m, silently introducing a critical bug in cryptographic code.

Integer overflow is a concern in languages with fixed-width integers like C or Java. Although the final Bézout coefficients are bounded by roughly max(a, b), intermediate values during the computation can be larger, though they remain within O(max(a,b)). In Python this is not an issue due to arbitrary-precision integers, but in other languages you must use 64-bit integers even for 32-bit inputs. Confusing floor division with truncation toward zero for negative numbers is another subtle bug in some languages.

Best practices include: always use the iterative version for production code to avoid recursion limits; write comprehensive tests including coprime pairs, non-coprime pairs, negative numbers, zero inputs, and large Fibonacci pairs; clearly document whether your function returns a gcd that is always non-negative; and when computing modular inverses, explicitly validate coprimality and raise an error if no inverse exists. For cryptographic use, consider using a well-vetted library implementation rather than rolling your own, to avoid side-channel vulnerabilities.

Testing Checklist

• Test with small known values: (240, 46) → gcd 2, (35, 15) → gcd 5, (120, 23) → gcd 1
• Test coprime and non-coprime pairs, and verify a×x + b×y == gcd
• Test edge cases: (0, 5), (5, 0), (1, 1), (a, a), and large consecutive Fibonacci numbers
• Test negative inputs and ensure sign handling is correct
• For modInverse, test that (a × inverse) % m == 1 and that non-invertible inputs raise an error
• Benchmark with large integers (e.g., 1024-bit) to ensure performance is logarithmic

Code Readability Tips

Use descriptive variable names like old_r, r, old_s, s rather than single letters when implementing the iterative version, and add comments that state the invariant (ri = a×xi + b×yi). This makes the code self-documenting and easier to verify against the mathematical definition. Keep the GCD computation and modular inverse as separate functions for clarity and reusability.

10. Interview Questions

The extended euclidean algorithm is a favorite topic in technical interviews for roles involving algorithms, cryptography, or low-level systems programming. Interviewers use it to assess understanding of number theory, recursion, invariants, and complexity analysis. Below are common questions with guidance on how to approach them.

Q1: How would you compute the modular inverse of a modulo m, and when does it not exist?

This is the most frequently asked question. A strong answer explains that the modular inverse a⁻¹ mod m exists if and only if gcd(a, m) = 1 (they are coprime), and it is the integer x such that a×x ≡ 1 mod m. You would describe using the extended euclidean algorithm to find x and y with a×x + m×y = gcd(a, m). If the gcd is 1, then a×x ≡ 1 mod m, so x mod m is the inverse. Mention the need to normalize a negative x by returning x % m, and discuss the O(log min(a, m)) time complexity. Be prepared to code the iterative version on a whiteboard and handle the error case where gcd != 1.

Q2: Explain why the Extended Euclidean Algorithm is correct. What is the loop invariant?

Interviewers ask this to test your ability to reason about correctness, not just code. You should articulate the invariant: at each iteration, the current remainders satisfy ri = a×xi + b×yi. Explain initialization (r0 = a×1 + b×0, r1 = a×0 + b×1) and maintenance (ri+1 = ri-1 - qi×ri and the same update for coefficients preserves the invariant). Then argue termination (remainders strictly decrease and are non-negative, so they must reach zero) and conclusion (when rk = 0, rk-1 = gcd(a, b) = a×xk-1 + b×yk-1). Mentioning the recursive formulation and how coefficients transform (x = y', y = x' - floor(a/b)×y') also demonstrates deep understanding.

Q3: What is the time complexity of the Extended Euclidean Algorithm and what is the worst-case input?

Expect to answer O(log min(a, b)) arithmetic operations, or O(n²) bit operations for n-bit numbers. Explain that the worst case occurs for consecutive Fibonacci numbers, e.g., (Fₙ₊₁, Fₙ), because they produce the longest sequence of divisions where every quotient is 1, maximizing the number of steps. Cite Lamé's theorem (at most 5× number of digits) to show you know the theoretical bound. Contrast with the best case (one division when b divides a) and note that average case is also logarithmic. Also mention space complexity: O(1) iterative, O(log min(a,b)) recursive.

Q4: Solve the linear Diophantine equation ax + by = c. When does it have a solution?

This tests whether you can apply Bézout's identity. The equation has integer solutions if and only if gcd(a, b) divides c. The approach: first use the extended algorithm to find x0, y0 with a×x0 + b×y0 = gcd(a, b) = d. If d does not divide c, report no solution. If it does, scale the solution: x = x0 × (c/d), y = y0 × (c/d) is one particular solution. Then describe the general solution: x = x + k×(b/d), y = y - k×(a/d) for any integer k. Provide a concrete example, e.g., 120x + 23y = 7 has solutions because gcd=1 divides 7, while 6x + 9y = 5 has no solution because gcd=3 does not divide 5.

Q5: How would you implement a constant-time modular inverse to prevent timing attacks?

This advanced question targets security-aware roles. Explain that the standard extended algorithm has variable execution time depending on the number of division steps, which can leak information about the private key. Two common mitigations are: (1) use Fermat's Little Theorem with constant-time modular exponentiation (a^(p-2) mod p) when the modulus is prime, which has fixed-time exponentiation, or (2) use a constant-time variant of the binary extended GCD that always performs the same number of iterations (e.g., by iterating for a fixed number of steps based on bit length and using constant-time conditional swaps/moves instead of branches). Mention that in practice, you should use vetted libraries like OpenSSL or libsodium that already implement these protections, rather than implementing your own.

Preparing for these questions involves not just memorizing code, but understanding the underlying mathematics, being able to trace an example by hand, and discussing trade-offs and edge cases confidently. Practice coding both recursive and iterative versions without reference, and be ready to derive the coefficient update formula from first principles.