How do you find the modular inverse using the Extended Euclidean Algorithm?

If GCD(a, m) = 1 (i.e., a and m are coprime), then the modular inverse a⁻¹ mod m exists and equals the Bézout coefficient s (reduced modulo m so that it is positive). Specifically, from s·a + t·m = 1, we get s·a ≡ 1 (mod m), so a⁻¹ ≡ s (mod m).

How is the Extended Euclidean Algorithm used in RSA encryption?

In RSA, the private exponent d is the modular inverse of the public exponent e modulo λ(n) (Carmichael's totient). The Extended Euclidean Algorithm efficiently computes d = e⁻¹ mod λ(n), which is only possible because e is chosen to be coprime with λ(n). Without the Extended Euclidean Algorithm, RSA key generation would be impractically slow.

∞

Extended Euclidean Algorithm Calculator

GCD · Bézout Coefficients · Modular Inverse

Compute GCD(a, b) together with integers s and t satisfying s·a + t·b = GCD. Full iteration table and modular inverse when coprime.

Quick Examples

Integer a

Integer b

GCD(a, b)

—

Greatest Common Divisor

Bézout s

—

s · a + t · b = GCD

Bézout t

—

s · a + t · b = GCD

Mod Inverse a⁻¹ mod b

—

Only when GCD = 1

Bézout's Identity Verification

GCD(a, b) = s · a + t · b

Step-by-Step Iteration Table

Each row: dividend = quotient × divisor + remainder. The highlighted row is where the remainder first becomes 0 — the GCD is the divisor in that row.

Step	Dividend	Divisor	Quotient	Remainder	s	t

Back-Substitution Explanation

🔒

RSA Cryptography

Key generation via modular inverse

In RSA, to generate keys for modulus n = p × q and public exponent e, the private exponent d must satisfy e × d ≡ 1 (mod λ(n)). The Extended Euclidean Algorithm computes this modular inverse efficiently.

Example: e = 17, λ(n) = 3120
GCD(17, 3120) = 1 (coprime — inverse exists)
Extended GCD → d = 17⁻¹ mod 3120
17 × 2753 = 46801 = 15 × 3120 + 1 ≡ 1 (mod 3120)
∴ Private key d = 2753

✖

Solving Linear Diophantine Equations

Integer solutions to ax + by = c

The equation ax + by = c has integer solutions if and only if GCD(a, b) divides c. The Extended Euclidean Algorithm gives a particular solution (x₀, y₀), from which the general solution follows.

General solution (when GCD | c):
x = x₀ × (c / GCD) + k × (b / GCD)
y = y₀ × (c / GCD) − k × (a / GCD) for any integer k

🔑

Cryptographic Key Exchange

Diffie-Hellman & ElGamal foundations

Diffie-Hellman and ElGamal rely on modular arithmetic in cyclic groups. Decryption requires computing modular inverses — for example, ElGamal decryption computes s⁻¹ mod p where s is the shared secret. The Extended Euclidean Algorithm is the standard method for this computation.

ElGamal decryption: m = c₂ × (c₁ˢ)⁻¹ mod p
Inverse computed via Extended GCD(s, p)
Since p is prime, GCD(s, p) = 1 always holds (s < p)
∴ s⁻¹ mod p always exists for prime moduli

What Is the Extended Euclidean Algorithm?

The Extended Euclidean Algorithm is a powerful extension of the classical Euclidean Algorithm discovered by ancient Greek mathematician Euclid. While the basic Euclidean Algorithm finds the Greatest Common Divisor (GCD) of two integers a and b through repeated division, the extended version simultaneously computes two integer coefficients s and t — called Bézout coefficients — satisfying the linear combination:

s · a + t · b = GCD(a, b)

This identity, known as Bézout's Identity, guarantees that such integer coefficients always exist for any pair of integers. The extended algorithm achieves this without any additional division steps beyond those of the standard GCD computation.

Bézout's Identity Explained

Bézout's Lemma (or Bézout's Identity) states: for any integers a and b with GCD(a, b) = d, there exist integers s and t such that s · a + t · b = d. Furthermore, d is the smallest positive integer expressible as a linear integer combination of a and b.

The Bézout coefficients are not unique. If (s, t) is one pair, then (s + k · (b/d), t − k · (a/d)) is another valid pair for any integer k. The algorithm returns the pair with the smallest absolute values.

How the Algorithm Works Step by Step

The algorithm runs the same division loop as basic GCD, but tracks two extra sequences (s_i) and (t_i) that satisfy r_i = s_i · a + t_i · b at every step. The recurrence is:

r_i+1 = r_i-1 − q_i × r_i (standard GCD step)
s_i+1 = s_i-1 − q_i × s_i
t_i+1 = t_i-1 − q_i × t_i

Starting from (r₀, s₀, t₀) = (a, 1, 0) and (r₁, s₁, t₁) = (b, 0, 1), the algorithm terminates when r_i = 0. The previous values (r_i-1, s_i-1, t_i-1) give the GCD and Bézout coefficients.

Time Complexity — Lamé's Theorem

The Extended Euclidean Algorithm has time complexity O(log min(a, b)). This follows directly from the basic Euclidean Algorithm's complexity. The key result is Lamé's Theorem (1844): the number of division steps never exceeds 5 times the number of decimal digits in the smaller input. Since each step computes at most 3 extra subtractions/multiplications, the total work remains O(log min(a, b)).

For comparison, a naive search for Bézout coefficients by exhaustive methods would be exponential. The Extended Euclidean Algorithm's logarithmic complexity makes it practical even for the enormous integers used in modern cryptography (1024–4096 bits).

Modular Inverse via Extended Euclidean Algorithm

The most important application is computing modular inverses. The modular inverse of a modulo m, written a⁻¹ mod m, is an integer x such that a × x ≡ 1 (mod m). It exists if and only if GCD(a, m) = 1.

When GCD(a, m) = 1, the Extended Euclidean Algorithm gives s · a + t · m = 1. Reducing modulo m: s · a ≡ 1 (mod m), so a⁻¹ mod m = s mod m (reduced to the range [0, m) if negative).

Reference Table: GCD, Bézout s, t for Common Pairs

a	b	GCD	s (Bézout)	t (Bézout)	Verification
252	105	21	-2	5	-2×252 + 5×105 = 21 ✓
35	15	5	1	-2	1×35 + (-2)×15 = 5 ✓
17	13	1	-3	4	-3×17 + 4×13 = 1 ✓
48	18	6	-1	3	-1×48 + 3×18 = 6 ✓
100	75	25	1	-1	1×100 + (-1)×75 = 25 ✓
1071	462	21	-9	21	-9×1071 + 21×462 = 21 ✓

Applications in Computer Science and Cryptography

RSA Encryption: Private key derivation requires computing d = e⁻¹ mod λ(n), directly solved by the Extended Euclidean Algorithm.
Chinese Remainder Theorem (CRT): Reconstructing solutions from a system of congruences requires modular inverses at each step.
Diffie-Hellman / ElGamal: Decryption operations in these schemes rely on modular inverses modulo large primes.
Linear Diophantine Equations: Any equation ax + by = c with integer solutions can be solved using Bézout coefficients as a particular solution.
Fraction Reduction in Modular Arithmetic: Computing a/b mod m as a × b⁻¹ mod m using the extended algorithm.
Error-Correcting Codes: Reed-Solomon and BCH codes use polynomial GCDs over finite fields, extending the same algorithm.

Frequently Asked Questions

What is the Extended Euclidean Algorithm?

The Extended Euclidean Algorithm extends the classical Euclidean GCD computation to also find integer Bézout coefficients s and t satisfying s · a + t · b = GCD(a,b). It achieves this in the same O(log min(a,b)) number of steps, making it highly efficient for cryptographic applications.

What are Bézout coefficients?

Bézout coefficients are integers s and t such that s · a + t · b = GCD(a, b). Their existence is guaranteed by Bézout's Identity for any pair of integers. They are not unique — infinitely many solutions exist, related by shifting: (s + k · b/GCD, t − k · a/GCD) for any integer k.

How do you find the modular inverse using Extended GCD?

If GCD(a, m) = 1 (a and m are coprime), run the Extended Euclidean Algorithm on a and m to get s · a + t · m = 1. Then a × s ≡ 1 (mod m), so a⁻¹ mod m = s mod m. If s is negative, add m to bring it into the range [0, m).

What is Bézout's Identity?

Bézout's Identity (Bézout's Lemma) states that for any two integers a and b with d = GCD(a, b), there exist integers s and t with s · a + t · b = d. Moreover, d is the smallest positive integer representable as an integer linear combination of a and b. This is a cornerstone result of elementary number theory.

When does the modular inverse not exist?

The modular inverse of a modulo m exists if and only if GCD(a, m) = 1 (a and m share no common factor except 1). If GCD(a, m) = d > 1, then a × x mod m cycles through multiples of d only and can never reach 1, so no inverse exists. In practice this means you must choose e coprime to λ(n) in RSA for the inverse to exist.

How is Extended GCD used in RSA encryption?

In RSA key generation, after computing modulus n = p × q and Euler's totient φ(n) = (p-1)(q-1), the private exponent d is computed as d = e⁻¹ mod φ(n) using the Extended Euclidean Algorithm. This is possible because e is chosen to be coprime with φ(n). Without this algorithm, computing the private key from the public exponent would be infeasibly slow.

What is the time complexity of the Extended Euclidean Algorithm?

The algorithm runs in O(log min(a, b)) time — the same as the standard Euclidean Algorithm. Lamé's Theorem guarantees the number of division steps is bounded by 5 times the number of decimal digits in the smaller number. Since each step does constant extra work to update the s and t sequences, the overall complexity is O(log min(a, b)) divisions and multiplications.