Number Theory | The GCD as a linear combination.

We prove that for natural numbers a and b, there are integers x and y such that ax+by=gcd(a,b). This is also called Bezout's Identity, although it was known by French Mathematician Claude Gaspard Bachet de Méziriac over 100 years before Bezout.

[yashuppot]

Wow, not only was that a completely different proof than the ones i have seen before, it was much more intuitive, thank you.

[davidbrisbane]

@3:30 ... I think this should be ... Since S is a nonempty set of positive integers, it has a minimum element  d=ax+by by the *Well-ordering principle* rather than by the Archimedian principle.

[PunmasterSTP]

Greatest Common Divisor? More like Greatest, Coolest Description! Thanks so much for making all of these wonderful videos, and then sharing them.

[omarshaaban]

first time i've seen such an approach to this identity. amazing work! thank you from Lebanon

[tushargarg]

I just started the book by Joseph Gallian and got stuck on this proof. This video is really helpful. Thanks a lot.

[hjdbr]

Excelent proof. Huge thanks from Brazil!

[georgesadler]

Professor M. Penn, thank you for a classic topic and selection of The GCD as a linear combination.

[wl]

This guy does a good job talking through proofs. And from the videos I've watched, he subtlety gives motivation for definitions and theories. Which I think is a sizable pitfall in teaching modern mathematics.

[atirmahmood]

Sir your explanations just make fall in love

[theunknown]

I'm working on Richard Hammack's book of proof and this video is a great compliment.

[jamesfortune]

That proof was so intellectually satisfying!

[davidbrisbane]

Is Michael on the bridge of the USS Enterprise?

[popcorn]

Nice! It took me a few watches, but I get it now. Excellent work thank you!

[sabirseikh]

Finally found a proof huhh all the other YouTubers are just giving examples

[holyshit]

In the CLRS Introduction to algorithms there is recursive algorithm for this

[proofbybri]

Why do we get the contradiction for r<d ?

[thomhughes]

I’m a bit confused about having c|d implies d=gcd(a, b).

Is it because we can apply this reasoning of c|d for any common divisor of a and b and the smallest number d for which this holds is by definition the gcd(a, b)?

[SANI-spgq]

Congratulations for 100k familys of mathematics.

[markbracegirdle]

You can illustrate this on a spreadsheet, iteratively subtracting the small number from the larger. Eventually one of them is zero, and the other must be the GCD.

[tilek]

Wow, I remember seeing this proof in my math circle and not really understanding anything.