Hello everyone. In this video, I'd like to talk about the following problem.
Let a, b, c be integers such that c divides a b,
and show that c divides the product of the gcds
of a and c, and the gcd of b and c.
I really would suggest, recommend,
strongly suggest that you stop the video now
and actually try this problem out. Try a couple of things and see what you come up with.
Then hopefully once you've tried a couple of things, watching this video
might give you a little bit of insight to some of the things that I tried,
got wrong, and then had to correct.
So it might be worth it to take a minute to do that
and then come back to the video.
Now I wanted to show this example
and I want to do it sort of stream of consciousness,
which is going to be hard to do because I've already solved this question,
but that being said I want to try to talk about my thought process when I first went through this question.
My thought process went a little something like this: so
I started off with the assumption that okay well c divides a b so
since c divides a b,
there exists an integer
k such that c k equals a b.
So this is how I started, c divides a b so
there exists an integer k such that c k equals a b.
I got to here,
I looked and I said, “okay this is true, but now the problem is
that I don't
really know how to get from here to some sort of gcd statement.”
So I sat, I looked at this for a little bit,
and I wasn't sure what to do.
So when I was stuck I said, “okay well I'm just going to get rid of this idea.”
Didn't work, it seems like a reasonable place to start but it's not going to help me.
So instead of doing that, let’s try to deal with one of the gcd conditions.
So let's deal with the gcd of a and c, okay?
I start at the gcd of a and c, that doesn't really give me much on its own,
so I need to get some other variables involved and I thought
well okay let’s try to use Bézout’s Lemma or the Extended Euclidean Algorithm.
So by Bézout’s Lemma,
EEA in the notes,
there exists integers x and y such that
a x plus c y is equal to the gcd of a and c.
Okay, that’s a reasonable starting point. So now I have some of the things I need,
some of the terms are here, this is looking like there's some potential here.
Now I have that c divides a b,
but there's no b’s here so maybe I should include them.
So let's multiply by b.
Okay so what am I going to get when I multiply by b?
So I get a b x plus c b y is equal to
b times the gcd of a and c.
This is good, now let's use the fact that c divides a b.
So c divides a b x,
so c divides a b, and c divides
c
so by Divisibility
of Integer Combinations,
c divides a b x plus c b y which is equal to
b gcd of a and c.
By the way I don't know where this is going, but at least
I'm getting there.
So c divides b times the gcd of a and c.
Let me put this in brackets,
one more little fix. Okay?
How do I know this is going to work? I don’t. I was kind of going through this blindly and I got to this,
okay, so c divides
b times the gcd of a and c.
Now I need the gcd of b and c to show up.
And I know that
the gcd of b and c divides b,
so what do I know? So then since…
Now I'm going to write b as
k times the gcd of b and c for some integer k,
possible since
gcd of b and c divides b.
So far, so good.
Alright now what? Well let's plug that in.
Okay well let's see what we have.
Substitute this above
and we're going to get
this.
So let's see where we are. c divides a b x plus c b y,
I guess I don't need that anymore. Let's just get rid of the first part.
So c divides just k times
gcd of b and c
and the gcd of a and c.
Okay so we reach this point
and then we see that c divides k times the gcd of b c times the gcd of a c,
but we really don't have a great reason to believe the gcd -
like really what we would you like to show is the gcd of c and k is 1,
but there's no real great way to do this.
So at this point, we're kind of in a tricky spot.
So we went down a wrong path,
now we're going to have to backtrack and correct that.
So how do we do that? Well
we introduced the b by going up here, multiplying by b yields this, right?
Now we made some progress but we got a little bit hosed at the end.
So let's try to remember okay we want the product of gcd of a and c and the gcd of b and c to appear.
Right?
And not until near the end do we introduce the gcd of b and c,
so let's actually do that at an earlier step.
So instead of multiplying by b, let's use Bézout’s Lemma again and see what we get.
So using
Bézout’s Lemma
again,
there exist integers, let’s say u and v,
such that…
let's say b u plus c v
is equal to the gcd of b and c.
Okay so now we have these two gcds,
let's multiply this together.
Multiply the previous two equations together
to see that a b x u
plus a c x v
plus
b c u y
plus c squared y v
is equal to the gcd of a and c
and the gcd of b and c.
So let's see what we got here.
So multiply the previous two equations together to see the following.
Okay now this looks a little bit more promising,
right, now let's look at the left-hand side, right?
c divides three of these values,
and in fact, c divides the first one too because c divides a b, alright.
So we can put it all together. Notice that up to this point we hadn't used the fact
that c divides a b, but let's do that now.
So...
write c k equals a b
for some integer k.
Substituting above and factoring
yields…
exactly what we want.
Let's see.
So substitute and factor, and now we see that c
times some integer is equal to the gcd of a c times the gcd b c,
that's exactly what we needed to show.
So let's just put in our concluding statement.
Okay so hopefully you stuck around this is a
tricky-ish problem, but I mean,
you kind of just have to go through it and try a couple of things. Sometimes you're going to be wrong
and eventually
you just kind of see it. There’s really no other way to explain it.
So how did we do this? Well
we used Bézout’s Lemma not once but twice,
multiplied these equations together,
and we got a whole bunch of terms, many of them depending on c,
and then this is extra factor a b.
Writing c k equals a b for some integer [k], we can substitute above
and see that c times an integer is equal to the product of the gcds
and thus c must divide the two gcds.
So hopefully you learned something about, you know, being wrong it's okay.
Stumbling through a problem, all of these things are okay.
The point is that you keep persisting
and hopefully something clicks and you just kind of
get the right sequence of statements to get the result that you want.
So I guess that's all I have to say.