Bézout's identity

What Is Bézout's Identity?

Why does this matter?

• It proves the GCD is expressible as an integer linear combination
• It's the foundation for the Extended Euclidean Algorithm
• It's used to solve linear Diophantine equations
• It shows why the GCD is the "smallest positive" linear combination

Derivation From First Principles

Let's prove Bézout's Identity from scratch.

Step 1: Define the set of all linear combinations

Let $S = \{ax + by : x, y \in \mathbb{Z}, \, ax + by > 0\}$

This is the set of all positive integers we can make by combining $a$ and $b$.

Why this set? We want to find the smallest positive number expressible as $ax + by$. We'll show this smallest number IS the GCD.

Step 2: Show $S$ is non-empty

Since $a$ and $b$ are not both zero, we can pick combinations that are positive:

• If $a > 0$: choose $x = 1, y = 0$ giving $a \in S$
• If $a < 0$: choose $x = -1, y = 0$ giving $-a = |a| \in S$

So $S$ contains at least $|a|$ or $|b|$. ✓

Step 3: Let $d$ be the smallest element of $S$

By the Well-Ordering Principle, $S$ has a smallest element. Call it $d$.

Since $d \in S$, we can write: $d = ax_0 + by_0$ for some integers $x_0, y_0$.

Step 4: Prove $d$ divides both $a$ and $b$

Claim: $d \mid a$

Proof by contradiction: Apply the Division Algorithm to $a$ and $d$: $a = qd + r \quad \text{where } 0 \le r < d$

Substitute $d = ax_0 + by_0$: $a = q(ax_0 + by_0) + r$ $r = a - q(ax_0 + by_0) = a(1 - qx_0) + b(-qy_0)$

Why this step? We've expressed $r$ as a linear combination of $a$ and $b$.

If $r > 0$, then $r \in S$ (it's a positive linear combination). But $r < d$, contradicting the fact that $d$ is the smallest element of $S$.

Therefore $r = 0$, so $d \mid a$. ✓

By identical reasoning, $d \mid b$. ✓

Step 5: Prove $d$ is the GCD

We've shown $d$ is a common divisor of $a$ and $b$.

Now let $c$ be any common divisor of $a$ and $b$. Then:

• $c \mid a \implies a = cm$ for some integer $m$
• $c \mid b \implies b = cn$ for some integer $n$

Therefore: $d = ax_0 + by_0 = cmx_0 + cny_0 = c(mx_0 + ny_0)$

So $c \mid d$.

Why this matters: Any common divisor divides $d$, so $d$ is the greatest common divisor.

Thus $d = \gcd(a, b)$ and we have: $\gcd(a, b) = ax_0 + by_0$

This completes the proof. □

Finding Bézout Coefficients: Extended Euclidean Algorithm

The Back-Substitution Method

Non-Uniqueness of Bézout Coefficients

Why? Let $d = \gcd(a,b)$. Starting from $ax_0 + by_0 = d$:

$a\left(x_0 + k \cdot \frac{b}{d}\right) + b\left(y_0 - k \cdot \frac{a}{d}\right) = ax_0 + by_0 + ak\frac{b}{d} - bk\frac{a}{d} = d +0 = d$

The extra terms cancel! This generates infinitely many coefficient pairs.

Common Mistakes

Applications

1. Solving Linear Diophantine Equations

The equation $ax + by = c$ has integer solutions if and only if $\gcd(a,b) \mid c$.

If $ax_0 + by_0 = \gcd(a,b)$, then multiply by $\frac{c}{\gcd(a,b)}$ to get a solution.

2. Modular Inverses

If $\gcd(a, m) = 1$, then $ax + my = 1$ has solutions. This means $ax \equiv 1 \pmod{m}$, so $x$ is the multiplicative inverse of $a$ modulo $m$.

3. Coprimality Proof

Bézout's Identity provides an alternative characterization of coprimality: $\gcd(a,b) = 1 \iff \exists x, y \in \mathbb{Z} : ax + by = 1$

Active Recall Flashcards

#flashcards/maths

What does Bézout's Identity state? :: For any integers $a$ and $b$ (not both zero), there exist integers $x$ and $y$ such that $ax + by = \gcd(a,b)$.

What is the key insight in proving Bézout's Identity? :: Consider the set $S$ of all positive linear combinations $ax + by$. The smallest element of $S$ is the GCD, by the Well-Ordering Principle and divisibility arguments.

Connections

• Euclidean Algorithm — Bézout coefficients are found by extending this algorithm
• Extended Euclidean Algorithm — The computational method for finding $x$ and $y$
• Linear Diophantine Equations — Bézout's Identity determines solvability
• Modular Arithmetic — Used to compute modular inverses
• Greatest Common Divisor — Bézout's Identity provides an alternative characterization
• Coprime Integers — Special case when $\gcd(a,b) = 1$

Concept Map

Hinglish (regional understanding)