Number System

Bézout’s Identity

A pupil combines measuring strips to match a target length.

Bézout’s Identity definition

Bézout’s identity says the greatest common divisor of two integers can be written as an integer linear combination of them.

In Spanish
identidad de Bézout
Topic
Number theory

Bézout’s Identity in a picture

Bézout’s Identity diagramBack-substitute a remainder to express the gcd using the original two numbers.18 = 48 − 30First remainder12 = 30 − 18Next remainder6 = 18 − 12 = 2·48 − 3·30The gcd as a linear combination
Back-substitute a remainder to express the gcd using the original two numbers.

How it works

If a and b are not both zero, some integers x and y satisfy ax + by = gcd(a, b). Work backward through the Euclidean algorithm to find such coefficients. When a and b are coprime, the right side is 1. This gives modular inverses and helps solve integer equations.

Worked examples

Write gcd(12, 8) as a combination.

4 = 12 − 8.

Write gcd(7, 3) as a combination.

1 = 7 − 2 × 3.

Use 1 = 7 − 2 × 3 to find an inverse of 3 modulo 7.

−2 ≡ 5 (mod 7), so 5 is an inverse.

Common mistake

The coefficients can be negative and need not be unique. Check the final combination equals the gcd.

Quick check

What type of coefficients does the identity use?

Show answer

Integers.

What is the right side for coprime inputs?

Show answer

1.

What algorithm can produce the coefficients?

Show answer

The extended Euclidean algorithm.

Sources

Flashcard

Bézout’s Identity

Reveal the definition

Bézout’s identity says the greatest common divisor of two integers can be written as an integer linear combination of them.

Effortless Math. “Bézout’s Identity.” Math Dictionary.