Bézout's Theorem — Definition, Formula & Examples

Bézout's Theorem (also called Bézout's Identity) is the guarantee that for any two integers

a

and

b

, you can always find integers

x

and

y

such that

ax + by = \gcd(a, b)

. The integers

x

and

y

are called Bézout coefficients, and they can be found using the Extended Euclidean Algorithm.

Let $a, b \in \mathbb{Z}$ , not both zero, and let $d = \gcd(a, b)$ . Then there exist integers $x, y \in \mathbb{Z}$ such that $ax + by = d$ . Moreover, $d$ is the smallest positive integer expressible as an integer linear combination of $a$ and $b$ , and every integer linear combination $ax + by$ is a multiple of $d$ .

Key Formula

ax + by = \gcd(a, b)

Where:

$a, b$ = Given integers (not both zero)
$x, y$ = Bézout coefficients (integers guaranteed to exist)
$\gcd(a,b)$ = Greatest common divisor of a and b

How It Works

To find the Bézout coefficients, apply the Extended Euclidean Algorithm: run the standard Euclidean Algorithm to compute

\gcd(a, b)

, then back-substitute to express the gcd as a linear combination of

a

and

b

. The coefficients are not unique — if

(x_0, y_0)

is one solution, then

(x_0 + kb/d,\; y_0 - ka/d)

is also a solution for any integer

k

. A key consequence is that

ax + by = c

has integer solutions if and only if

\gcd(a, b)

divides

c

Worked Example

Problem: Find integers x and y such that 36x + 15y = gcd(36, 15).

Step 1: Apply the Euclidean Algorithm to find gcd(36, 15).

36 = 2 \cdot 15 + 6, \quad 15 = 2 \cdot 6 + 3, \quad 6 = 2 \cdot 3 + 0

Step 2: The last nonzero remainder is 3, so gcd(36, 15) = 3. Now back-substitute to express 3 as a combination of 36 and 15.

3 = 15 - 2 \cdot 6

Step 3: Replace 6 with (36 − 2·15) from the first equation.

3 = 15 - 2(36 - 2 \cdot 15) = 5 \cdot 15 - 2 \cdot 36

Step 4: Rewrite in the form 36x + 15y = 3.

36(-2) + 15(5) = 3

Answer: x = −2, y = 5, since 36(−2) + 15(5) = −72 + 75 = 3 = gcd(36, 15).

Why It Matters

Bézout's Theorem is the foundation for proving that modular inverses exist:

a

has an inverse modulo

n

precisely when

\gcd(a, n) = 1

. This makes it essential in cryptography (RSA key generation), solving linear Diophantine equations, and proofs throughout number theory courses.

Common Mistakes

Mistake: Assuming that ax + by = c always has integer solutions for any integer c.

Correction: Integer solutions exist only when gcd(a, b) divides c. For example, 4x + 6y = 5 has no integer solutions because gcd(4, 6) = 2 does not divide 5.