Bézout’s lemma

Bézout’s lemma is the statement that GCD is a linear combination.

Given nonzero integers $𝑎, 𝑏$ , then there exists $𝑠, 𝑡 \in ℤ$ such that $g c d (𝑎, 𝑏) = 𝑠 𝑎 + 𝑡 𝑏$ . #m/thm/num

Sometimes this is stated with the additional property that $g c d (𝑎, 𝑏)$ is the smallest positive integer of this form, thus for all $𝑎, 𝑏 \in ℕ$

g c d (𝑎, 𝑏) = m i n {𝑠 𝑎 + 𝑡 𝑏 ∣ 𝑠, 𝑡 \in ℕ, 𝑠 𝑎 + 𝑡 𝑏 > 0}

This extra property can be proven by the fact that any linear combination of the form $𝑠 𝑎 + 𝑡 𝑏$ is some multiple of $g c d (𝑎, 𝑏)$ .

Bézout’s lemma can be used to prove Euclid’s lemma. The integers $𝑠, 𝑡$ can be found by Extended Euclid’s algorithm

For relative primes

A corollary of Bézout’s lemma is that if $𝑎$ and $𝑏$ are relatively prime then there exists $𝑠, 𝑡 \in ℤ$ such that $𝑠 𝑎 + 𝑡 𝑏 = 1$ .