Hello everyone. In this video, I'd like to talk about the following problem.
Let $a$, $b$, $c$ be integers such that $c \mid ab$. Show that $c\mid\gcd(a,c)\gcd(b,c)$.
I really would suggest, recommend, strongly suggest that you take a minute 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, reading this 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.
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\mid ab$ so since $c\mid ab$, there exists an integer $k$ such that $ck=ab$.
So this is how I started, 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 $\gcd(a,c)$. I start with $\gcd(a,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 exist integers $x$ and $y$ such that
$$ax+cy=\gcd(a,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\mid ab$, but there's no $b$’s here so maybe I should include them. So let's multiply by $b$.
Multiplying by $b$ yields
$$abx+cby=b\gcd(a,c)$$This is good, now let's use the fact that $c\mid ab$. So $c\mid ab$, and $c\mid c$, so by Divisibility of Integer Combinations,
$$c\mid(abx+cby)=b\gcd(a,c)$$By the way I don't know where this is going, but at least I'm getting there. 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\mid b\gcd(a,c)$.
Now I need $\gcd(b,c)$ to show up. And I know that $\gcd(b,c)\mid b$, so let's write $b=k\gcd(b,c)$ for some integer $k$ possible since $\gcd(b,c)\mid b$.
So far, so good. Alright now what? Well let's plug that in.
$$c\mid k\gcd(b,c)\gcd(a,c)$$Okay so we reach this point and then we see that $c\mid k\gcd(b,c)\gcd(a,c)$, but really what we would you like to show is $\gcd(c,k)=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 multiplying by $b$. Now we made some progress but we got a little bit hosed at the end.
So let's try to remember okay we want $\gcd(a,c)\gcd(b,c)$ to appear. And not until near the end do we introduce $\gcd(b,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.
By Bézout’s Lemma (EEA) again, there exist integers $u$ and $v$ such that
$$bu+cv=\gcd(b,c)$$Okay so now we have these two $\gcd$'s, let's multiply them together.
$$abxu+acxv+bcuy+c^2yv=\gcd(a,c)\gcd(b,c)$$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, right, and in fact, $c$ divides the first one too because $c\mid ab$, alright.
So we can put it all together. Notice that up to this point we hadn't used the fact that $c\mid ab$, but let's do that now. So write $ck=ab$ for some integer $k$. Substituting above and factoring yields
$$c(kxu+axv+buy+cyu)=\gcd(a,c)\gcd(b,c)$$Thus $c\mid \gcd(a,c)\gcd(b,c)$
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 $ab$. Writing $ck=ab$ for some integer $k$, we can substitute above and see that $c(kxu+axv+buy+cyu)=\gcd(a,c)\gcd(b,c)$ and thus $c\mid \gcd(a,c)\gcd(b,c)$.
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.