Bézout's identity: au + bv = gcd(a, b)

The theorem

Bézout’s theorem: for any integers $a, b$ not both zero, there exist integers $u, v$ such that:

$a u + b v = \gcd(a, b)$

Corollary: coprime integers

$a$ and $b$ are coprime iff there exist integers $u, v$ with:

$a u + b v = 1$

Equivalent to $\gcd(a, b) = 1$.

Finding $u$ and $v$: extended Euclid

1. Run the Euclidean algorithm (successive divisions).
2. Go back up expressing each remainder as a combination of $a$ and $b$.

Example: Bézout for $a = 30$, $b = 18$

Euclid descent:

• $30 = 1 \times 18 + 12$
• $18 = 1 \times 12 + 6$
• $12 = 2 \times 6 + 0$ ⇒ gcd = 6.

Back-substitution:

• $6 = 18 - 12$
• $6 = 18 - (30 - 18) = 2 \times 18 - 30$

So $u = -1$, $v = 2$: $30 \times (-1) + 18 \times 2 = 6$. ✓

Application 1: Diophantine equation

Solve $ax + by = c$ in $\mathbb{Z}$:

• Has a solution iff $\gcd(a, b) \mid c$.
• If so: find a particular solution by Bézout, then all others by induction.

Application 2: modular inverse

Find $u$ with $a u \equiv 1 \pmod n$?

Exists iff $\gcd(a, n) = 1$. By Bézout: $a u + n v = 1$, so $a u \equiv 1 \pmod n$.

GCD is smallest positive

The gcd is the smallest positive integer of the form $au + bv$ with $u, v \in \mathbb{Z}$.

Common mistakes

1. Confusing Bézout and Gauss (Gauss = if $a | bc$ and $\gcd(a,b)=1$ then $a | c$).
2. Forgetting $u, v$ can be negative.
3. Searching $u, v$ in $\mathbb{N}$ (often impossible).

?À toi de jouer

Do integers u, v exist with 15u + 25v = 4?

A.No (gcd = 5, does not divide 4)B.Yes, u = 1, v = 0C.Yes, u = 4, v = −2D.Always possible

Valider