mindevice
Discrete Structures

Extended Euclidean Algorithm

Computes the greatest common divisor of two integers together with the Bézout coefficients λ and μ — optionally in ℤ_p to find a modular inverse.

Result

gcd(252, 198) = 18

Bézout representation: 18 = 4 · 252 + -5 · 198

Steps

StepDivisionλμ
1252 = 1 · 198 + 5410
2198 = 3 · 54 + 3601
354 = 1 · 36 + 181-1
436 = 2 · 18 + 0-34

Explanation

Motivation

The Euclidean algorithm finds the greatest common divisor (gcd) of two integers by repeated division with remainder. The extended Euclidean algorithm does more: alongside the gcd it returns two integer coefficients λ\lambda and μ\mu that express the gcd as a linear combination of the two inputs. These coefficients are exactly what you need to compute a multiplicative inverse in Zp\mathbb{Z}_p — the basis of RSA, of solving linear congruences, and of the Chinese remainder theorem.

Formal definition

For a,b∈Za, b \in \mathbb{Z}, Bézout's lemma guarantees integers λ,μ\lambda, \mu with

λ⋅a+μ⋅b=gcd⁡(a,b).\lambda \cdot a + \mu \cdot b = \gcd(a, b).

The extended Euclidean algorithm constructs such a pair (λ,μ)(\lambda, \mu) explicitly. It performs the Euclidean division

a=q⋅b+r,0≤r<b,a = q \cdot b + r, \qquad 0 \le r < b,

iteratively, replacing (a,b)(a, b) by (b,r)(b, r) at each step. In parallel it carries the coefficients through the recurrence

λk+1=λk−1−qk λk,μk+1=μk−1−qk μk\lambda_{k+1} = \lambda_{k-1} - q_k\,\lambda_k, \qquad \mu_{k+1} = \mu_{k-1} - q_k\,\mu_k

starting from (λ0,μ0)=(1,0)(\lambda_0, \mu_0) = (1, 0) and (λ1,μ1)=(0,1)(\lambda_1, \mu_1) = (0, 1). When the remainder reaches 00, the previous value is the gcd, and its λ,μ\lambda, \mu satisfy the Bézout identity.

Modular inverse in Zp\mathbb{Z}_p

If gcd⁡(a,p)=1\gcd(a, p) = 1, then λ⋅a+μ⋅p=1\lambda \cdot a + \mu \cdot p = 1 immediately gives

λ⋅a≡1(modp),\lambda \cdot a \equiv 1 \pmod{p},

so λ\lambda (reduced into [0,p)[0, p)) is the inverse a−1a^{-1} in Zp\mathbb{Z}_p. In the calculator, find it by setting b=pb = p and the modulus pp.

Worked example

Take the standard example a=252a = 252, b=198b = 198 — the calculator's default above. The divisions with remainder are:

252=1⋅198+54198=3⋅54+3654=1⋅36+1836=2⋅18+0\begin{aligned} 252 &= 1 \cdot 198 + 54 \\ 198 &= 3 \cdot 54 + 36 \\ 54 &= 1 \cdot 36 + 18 \\ 36 &= 2 \cdot 18 + 0 \end{aligned}

The last non-zero remainder is gcd⁡(252,198)=18\gcd(252, 198) = 18. Back-substituting yields the Bézout representation

18=4⋅252+(−5)⋅198,18 = 4 \cdot 252 + (-5) \cdot 198,

so λ=4\lambda = 4 and μ=−5\mu = -5. These are exactly the values shown in the calculator's step table.

Common pitfalls

  • Forgetting signs: λ\lambda or μ\mu is often negative. Over Z\mathbb{Z} that is correct; only for an inverse in Zp\mathbb{Z}_p do you reduce into [0,p)[0, p).
  • Wrong remainder range: Euclidean division requires 0≤r<b0 \le r < b. A negative remainder produces a wrong sequence of steps.
  • Inverse without coprimality: a−1a^{-1} exists in Zp\mathbb{Z}_p only when gcd⁡(a,p)=1\gcd(a, p) = 1. Otherwise the congruence ax≡1a x \equiv 1 has no solution.
  • Swapping aa and bb: the gcd is unchanged, but λ\lambda and μ\mu swap roles — keep track of which coefficient belongs to which number.