Bezout Identity

The Key Result

Why It Works

1. 1
   Let $d$ be the smallest positive integer of the form $ax + by$ with $x, y \in \mathbb{Z}$.
2. 2
   Dividing $a$ by $d$ gives $a = qd + r$ with $0 \le r < d$; then $r = a - qd = a(1 - qx) + b(-qy)$ is also a combination of $a$ and $b$.
3. 3
   Since $r < d$ and $d$ is the smallest positive such combination, $r = 0$, so $d \mid a$; similarly $d \mid b$.
4. 4
   Any common divisor of $a$ and $b$ divides $ax + by = d$, so $d = \gcd(a,b)$. The coefficients $x, y$ come from running the Euclidean algorithm backward.

Worked Examples

Going Deeper

• Generalization: Bézout extends to several integers — $\gcd(a_1, \dots, a_k)$ is the least positive value of $a_1 x_1 + \cdots + a_k x_k$ — and is the source of the fact that $\gcd(a,b) = 1 \iff ax+by=1$, which characterizes when modular inverses and the Chinese Remainder Theorem apply.
• Where it appears: computing modular inverses (solve $ax + ny = 1$, then $x \equiv a^{-1} \pmod n$), constructing CRT solutions, proving coprimality, and the existence half of solving linear Diophantine equations $ax + by = c$.
• Pitfall: the coefficients $x, y$ are NOT unique — you can add $(b/g, -a/g) \cdot t$ to any solution. Beginners also overreach: $ax + by = c$ is solvable iff $\gcd(a,b) \mid c$, so $ax+by=1$ requires $\gcd(a,b) = 1$ exactly; if the gcd is $g > 1$ the smallest positive combination is $g$, not $1$.

Spot the Signal

• Look for problems where the key step is expressing gcds as integer linear combinations to prove existence and solve congruences.
• You can describe the hard part as expressing gcds as integer linear combinations to prove existence and solve congruences, but a direct attack starts producing clutter.
• The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

• Start by identify the integer constraint that calls for bezout identity, then rewrite the givens around it.
• Name the relation that makes Bezout Identity legal before doing computation.
• Use the new relation to replace the messiest part of the problem with a cleaner one.
• Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

• Do not use Bezout Identity just because the surface looks familiar; verify the required condition first.
• Applying Bezout Identity because it sounds relevant, without checking the trigger first.
• Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note