Hello everyone. So in this video, I'd like to prove the following proposition.
I didn't prove this in class, but I alluded to its truth.
Now I'll actually demonstrate it.
So d divides a and d divides b then d divides the gcd of a and b
It's perhaps kind of tough to know where to start; it really is.
d divides a and d divides b doesn't really tell us too much,
Right? We need to use something about the gcd here
in order to get the last division. So we're gonna start with the gcd.
I usually write a letter for the gcd, just to make my life easier,
and so that I don't have to write gcd a hundred times.
So let e equal the gcd of a and b.
Now what am I gonna do? Well,
we have some hammers from class, so let's try to use one,
and the one I'm going to use is Bezout's Lemma, so the back substitution.
"By Bezout's Lemma,
we know there exist integers x and y
such that:
e is equal to a x plus b y."
Alright so that's what Bezout's Lemma says.
It says that you can write the gcd as a linear combination of a and b.
Okay, so now with this hammer in place, the proof is in good shape.
So now, let's actually use the hypothesis,
which is d divides a and d divides b.
Since d divides a and d divides b,
by divisibility of integer combinations,
we have...
d divides...let's take a good linear combination of a and b,
and the ones that we should do is the x and y linear combination
a x plus b y and that's equal to e.
Since e was equal to the gcd of a and b,
we're actually done.
Thus... let's see this in action…
so, d divides a x plus b y and a x plus b y is e which is the gcd of a and b.
So thus, d divides
the gcd of a and b.
And that's it.
A quick little theorem here.
So here we didn't have to use too too much but,
we did use a combination of some of the hammers that we have:
Bezout's Lemma and divisibility of integer combinations.
Those two things combined, take us home in this problem.
So again, it's tough to know where to start in a problem like this.
Again sometimes it helps to look at the conclusion,
sometimes it doesn't, it really just depends.
But here since we want d divides the gcd of a and b,
it makes sense to try to do something with the gcd of a and b,
and what can we do? Well, back substitution
or Bezout's Lemma or whatever you want to call it,
that gives us integers x and y; we can get the ball rolling with that.
Hopefully this has been enlightening.
Thank you very much for your time. Good luck.