Number theory MOC

Bézout’s lemma

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

Given nonzero integers , then there exists such that . #m/thm/num

Sometimes this is stated with the additional property that is the smallest positive integer of this form, thus for all

This extra property can be proven by the fact that any linear combination of the form is some multiple of .

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 such that .

Practice problems

• 2017. Contemporary abstract algebra, p. 25 (§0 exercises p, 4, 8, 10…)

---

tidy| en | sembr