Course contentsShow
← Mathematics
Lesson 2715 of 3,12154. Number TheoryFree lesson

Extended Euclidean Algorithm

Discover how to express the GCD as a linear combination of the two original integers.

Extended Euclidean Algorithm

What you'll learn: How to express the greatest common divisor (GCD) of two integers as a linear combination of those integers.

The Core Idea

The Euclidean Algorithm gives you the GCD of two numbers, but the Extended Euclidean Algorithm goes further: it finds integers x and y such that:

gcd(a, b) = ax + by

This equation is called a linear combination or Bézout's identity. It's incredibly useful in number theory—showing that you can "build" the GCD using the original numbers themselves.

How It Works

The Extended Euclidean Algorithm works backward through the steps of the regular Euclidean Algorithm. Here's the intuition:

  1. Run the standard Euclidean Algorithm forward, keeping track of all remainders
  2. Starting from the last nonzero remainder (the GCD), express it in terms of the previous two remainders
  3. Work backward, substituting each remainder until you express the GCD purely in terms of the original a and b

Example

Find gcd(240, 46) and express it as a linear combination:

Forward (Euclidean Algorithm):

  • 240 = 46 × 5 + 10
  • 46 = 10 × 4 + 6
  • 10 = 6 × 1 + 4
  • 6 = 4 × 1 + 2
  • 4 = 2 × 2 + 0

So gcd(240, 46) = 2.

Backward (Extended):

  • 2 = 6 − 4 × 1
  • 2 = 6 − (10 − 6 × 1) × 1 = 6 × 2 − 10
  • 2 = (46 − 10 × 4) × 2 − 10 = 46 × 2 − 10 × 9
  • 2 = 46 × 2 − (240 − 46 × 5) × 9 = 240 × (−9) + 46 × 47

Check: 240(−9) + 46(47) = −2160 + 2162 = 2 ✓

Key Takeaway: The Extended Euclidean Algorithm not only finds gcd(a, b) but also discovers coefficients x and y satisfying gcd(a, b) = ax + by, revealing the deep structure behind divisibility.