View source for SP20:Lecture 16 Bézout coefficients

In this lecture, we did 3 similar proofs: that the [[Claim:gcd(a,b) is a common divisor of a and b|GCD is a common divisor]], that it [[Claim:gcd(a,b) is greater than all other common divisors of a and b|is the greatest common divisor]], and that the [[Claim:Bézout coefficients exist|Bézout coefficients exist]].

* [[Redirect:FA17 Lecture 34|Last semester's notes]]
* [[Media:sp20-lec16-slides.pdf]]

= Greatest common divisor =

{{:Greatest common divisor}}

{{Claim:gcd(a,b) is a common divisor of a and b}}

{{Claim:gcd(a,b) is greater than all other common divisors of a and b}}

== Choosing an inductive priniple ==

We will prove both of these claims by [[induction]], but we have a choice to make: should we use induction on <math>a</math> or on <math>b</math> (or both?).

{{:Choosing an inductive principle}}

== gcd is a common divisor ==

{{Proof:gcd(a,b) is a common divisor of a and b}}

== gcd is the greatest common divisor ==

{{Proof:gcd(a,b) is greater than all other common divisors of a and b}}

= Bézout coefficients =

We used the last part of the lecture to prove a useful fact:

{{:Bézout coefficients}}