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

Computing Solutions Using Bézout Coefficients

Apply the extended Euclidean algorithm to find the modular inverses needed in the CRT construction.

Computing Solutions Using Bézout Coefficients

What you'll learn: How to use the extended Euclidean algorithm to find modular inverses that plug directly into the Chinese Remainder Theorem construction.

The Connection to CRT

When solving systems of congruences with the Chinese Remainder Theorem (CRT), you need to find modular inverses for each piece of the solution. Specifically, if you have moduli m₁, m₂, ..., mₖ and set M = m₁m₂...mₖ, then for each Mᵢ = M/mᵢ, you need the inverse of Mᵢ modulo mᵢ.

This is exactly where Bézout coefficients come in.

How It Works

Recall that Bézout's Identity guarantees that for coprime integers a and b, there exist integers x and y such that:

ax + by = gcd(a,b) = 1

When you need the inverse of Mᵢ (mod mᵢ), you apply the Extended Euclidean Algorithm to find coefficients satisfying:

Mᵢ · x + mᵢ · y = 1

Since the mᵢ · y term vanishes modulo mᵢ, you get:

Mᵢ · x ≡ 1 (mod mᵢ)

This means x is the modular inverse you need! It's the yᵢ coefficient in the CRT formula.

Example

Suppose you need the inverse of 35 modulo 12. Run the Extended Euclidean Algorithm:

  • 35 = 2(12) + 11
  • 12 = 1(11) + 1
  • Back-substitute: 1 = 12 - 1(11) = 12 - (35 - 2·12) = 3(12) - 1(35)

So 35·(-1) + 12·(3) = 1, meaning 35·(-1) ≡ 1 (mod 12).

Taking -1 ≡ 11 (mod 12), the inverse is 11.

Key Takeaway: The extended Euclidean algorithm directly produces the Bézout coefficient that serves as the modular inverse needed in each step of the CRT construction—no trial-and-error required.