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

Bézout's Identity

Understand that the GCD of two integers can always be written as an integer linear combination of them.

Bézout's Identity

What You'll Learn

You'll discover that the greatest common divisor (GCD) of two integers can always be expressed as an integer combination of those two numbers.

The Core Idea

Bézout's Identity states: For any two integers a and b (not both zero), there exist integers x and y such that:

ax + by = gcd(a, b)

This is a powerful statement. It tells us that the GCD isn't just some abstract "largest common divisor"—it's something we can actually construct using the two original numbers through addition, subtraction, and multiplication by integers.

Why This Matters

The Extended Euclidean Algorithm (which you just learned) is the practical tool that finds these coefficients x and y. Bézout's Identity is the theoretical guarantee that such coefficients always exist.

A Concrete Example

Consider a = 35 and b = 15. We know gcd(35, 15) = 5.

Bézout's Identity promises integers x and y where: 35x + 15y = 5

One solution: x = 1 and y = −2

  • Check: 35(1) + 15(−2) = 35 − 30 = 5 ✓

An Analogy

Think of a and b as two different-sized measuring cups. Bézout's Identity says that by filling and emptying these cups (adding and subtracting multiples), you can always measure out exactly one unit of their GCD—no more, no less.

Important Note

The coefficients x and y are not unique. There are infinitely many pairs that work! But at least one pair always exists.

Key Takeaway: Bézout's Identity guarantees that gcd(a, b) can always be written as an integer linear combination ax + by, and the Extended Euclidean Algorithm finds the coefficients x and y.