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

Bézout's Identity states that for any two integers

a

and

b

(not both zero), their greatest common divisor can be written as a linear combination

ax + by

for some integers

x

and

y

Let $a, b \in \mathbb{Z}$ with $(a, b) \neq (0, 0)$ . Then there exist integers $x, y$ such that $ax + by = \gcd(a, b)$ . Moreover, $\gcd(a, b)$ is the smallest positive integer expressible in this form, and every integer of the form $ax + by$ is a multiple of $\gcd(a, b)$ .

Key Formula

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

Where:

$a, b$ = Integers, not both zero
$x, y$ = Integer coefficients (Bézout coefficients)
$\gcd(a, b)$ = Greatest common divisor of a and b

How It Works

To find the coefficients

x

and

y

, apply the Extended Euclidean Algorithm. First, run the standard Euclidean Algorithm to compute

\gcd(a, b)

by repeated division. Then back-substitute each step to express the GCD as a combination of

a

and

b

. The coefficients

x

and

y

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

, where

d = \gcd(a, b)

Worked Example

Problem: Express gcd(48, 18) as a linear combination of 48 and 18.

Step 1: Apply the Euclidean Algorithm.

48 = 2 \cdot 18 + 12 \quad\Rightarrow\quad 18 = 1 \cdot 12 + 6 \quad\Rightarrow\quad 12 = 2 \cdot 6 + 0

Step 2: The last nonzero remainder is the GCD.

\gcd(48, 18) = 6

Step 3: Back-substitute to express 6 as a combination of 48 and 18. From the second equation: 6 = 18 − 1·12. From the first equation: 12 = 48 − 2·18. Substitute:

6 = 18 - 1(48 - 2 \cdot 18) = 3 \cdot 18 - 1 \cdot 48 = 48(-1) + 18(3)

Answer:

\gcd(48, 18) = 6 = 48(-1) + 18(3)

, so the Bézout coefficients are

x = -1

and

y = 3

Why It Matters

Bézout's Identity is the foundation for proving that if a prime

p

divides a product

ab

, then

p

divides

a

p

divides

b

— a key step toward the Fundamental Theorem of Arithmetic. It also underpins modular inverse computation, which is essential in RSA cryptography and solving linear congruences.

Common Mistakes

Mistake: Assuming the Bézout coefficients x and y are unique.

Correction: There are infinitely many pairs (x, y) satisfying the identity. The Extended Euclidean Algorithm finds one particular pair, and all others differ by multiples of b/d and a/d respectively.