This algorithm…actually… so this algorithm
we’ll learn… so in my section I'm going to teach this on…
next week's lecture,
on Monday’s lecture.
I'm going to teach the Extended Euclidean Algorithm,
but this process is also known as Bezout’s Lemma
the theorem states the following: “Let a and b be integers.
then there exists integers x and y such that
a x plus b y is equal to the gcd of a and b.'
What's the proof of this? Well the proof of this is
do the Euclidean Algorithm, and then do back substitution.
That's the like three line proof.
Now you could go through and algebraically break this down.
It is a little bit painful though, so I'm not going to.
You can check it out as extra reading. It’s definitely on Wikipedia,
I believe it's also in your course notes.
If not, again, it's on Wikipedia. It’s a very…
it's easily accessible, it's a very common proof.
but it is...
it is tedious there's no real reason -
if you understood the previous two slides, there's no reason to really formally prove this.
But if you're curious you can go check it out.
So that's Bezout’s Lemma.
Now when you have something like this, one question
you might want to ask is, “What about a converse type theorem?”
And a converse type theorem would look something like this:
the GCD Characterization Theorem.
So if I have some positive integer d,
and d divides a and d divides b where a and b are integers
and there exist integers x and y such that a x plus b y equals d,
so we have four conditions here that need to be satisfied. We need
d to be a positive integer,
we need d to be a common divisor of a and b,
and we need d to be an integer linear combination of a and b.
If all those things are true, then d is the greatest common divisor of a and b.
So if you want to think -
so let's think about maybe how would a proof go before I just show you the proof.
What would a proof look like? Well
I want to show d is equal to some gcd value,
so let's make some new letter e equal to gcd of a and b,
okay, so some non-given letter,
say e.
Now I'm trying to show that d is less than or equal to e and e is less than or equal to d.
Well e is a common divisor of a and b
so e divides a, e divides b,
therefore by Divisibility of Integer Combinations, once again, e must divide d
And now let's go in the opposite direction
What do we have? Well d divides a and d divides b, so therefore
d must be less than or equal to e because
e is the greatest common divisor of a and b.
So that's basically the idea here, so let's just take a look at it.
That's basically what I said, but I actually think I reversed it.
So let e be the gcd of a and b,
then since d divides a and d divides b, by definition
and the maximality of e, we have that d must be less than or equal to e, right?
e is the greatest common divisor of a and b and d is a common divisor of a and b.
Again, by definition, we see that e divides a and e divides b
so by Divisibility of Integer Combinations, we have that e divides
a linear combination of a and b,
specifically the given one.
This implies that e divides d.
So thus by Bounds By Divisibility, we know that
the absolute of e is less than or equal to the absolute value of d,
and here's where we needed the fact that d was positive,
it's right here, we only know that
the absolute value of e is less than or equal to the absolute value of d
and we really want that e is less than or equal to d,
and we get that because both of these things are positive.
So hence d equals e.
So something to note here, so my proofs and…
well my proofs and I think everyone's proofs who teaches this course,
are going to get a little bit… I’m going to say sloppier but
I don't want to… that's not really true.
If you're going to prove something directly, a lot of the times
mathematicians won't write, “Assume that
d is greater than 0 and d divides a
and d divides b and there exist integers x and y…”
it's kind of implied that okay well if I'm proving this and I don't
give you any indication that I'm doing something else, it's going to be a direct proof.
You know, if I want to prove something by contradiction,
maybe I'll mention, “Assume towards a contradiction…” something like that
but in a direct proof, I'm not going to rewrite the hypothesis every single time.
It's pretty clear that this is going to be -
well that this is a direct proof, so I don't need to rewrite it.
If you find that it helps you to rewrite the hypothesis, then I suggest
you go ahead and do that. That's perfectly fine.
But I'm going to try to steer away from doing that and try to write
mathematics now a little bit more how you would see it in a textbook and such.