Hello everyone. In this video, we're going to continue our exam review. So we have here question $4$.
Question Part $1$: If $a,b,c\in\mathbb{Z}$ with $c\mid ab$ and $\gcd(a,c)=1$ then $c\mid b$.
So with a question like this, since the $\gcd$ condition is in the hypothesis, I'm going to try to use Bézout’s Lemma and kind of get through this, okay? This is the condition that I'm going to start with, you could use divisibility and try to manipulate it, but I feel like this condition is the easiest to start with by using Bézout’s Lemma, or the Extended Euclidean Algorithm, whatever you call it. So because of that, let's go through it.
Since $\gcd(a,c)=1$, we may apply Bézout’s Lemma, or the Extended Euclidean Algorithm, to see that there are integers $x$ and $y$ such that:
$$ax+cy=1$$Now I want to show that $c\mid b$, and I know that $c\mid ab$, so I got to get $ab$ to appear in here. So in order to do that, I'm going to multiply everything by $b$, which gives
$$abx+cby=b$$So now $c\mid ab$, and $c\mid c$, so $c\mid cby$, and so by Divisibility of Integer Combinations, $c\mid b$. And that completes the proof. So that's good, that was not too, too bad.
Question Part $2$: For integers $a,b,c$ such that $\gcd(a,b)=1$ if $a\mid c$ and $b\mid c$ then $ab\mid c$.
When I look at this, intuitively I think of GCDPF because it is probably the most natural way to do it, right? So clearly, $a$ and $b$ must not share any prime factors, so if $a\mid c$ and $b\mid c$, and $a$ and $b$ don't share any prime factors, then $ab$ shoudl divide $c$.
So intuitively that's what I do, but I know that it's a nightmare to write down a GCDPF argument correctly. So I'm going to try to avoid that, and the way I'm going to do that is I'm going to try to get a little bit creative.
So again I know that $\gcd(a,b)=1$, so I'm going to throw it into the EEA, or Bézout’s Lemma whatever you want to call it, to show there exist integers $x$ and $y$ such that
$$ax+by=1$$Now once I have that $ax+by=1$, I’m in sort of a pickle, right, I don't really know what to do. So we know $a\mid c$ and $b\mid c$, so by definition there exist integers $m$ and $n$ such that $am=c$ and $bn=c$.
So I'm going to unwind the definition of divisibility, and try to use that with the combination of $ax+by=1$. So the combination of those two facts should get me somewhere.
Now I want $am$ and $bn$ to appear, so I should probably multiply everything by $mn$.
$$amnx+bmny=mn$$I don't know where this is going at this point, okay, so I'm actually taking this at blind faith and hoping that I'm going to get to an answer. Turns out that I'm going to, hopefully, but when I started writing the solution of this, I didn't know that. I just kind of said okay well I have these two things and I know that I'm going to multiply it, and hopefully something good is going to happen. That's sort of my thought process at this point.
So $am=c$, I’m going to substitute that in, and $bn=c$, so I'm going to substitute that in.
$$cnx+cmy=c(nx+my)=mn$$Since $c\mid mn$, by definition, there exists an integer $k$ such that $ck=mn$. Now what do we know? Let's go back to $am=c$.
Now I know that I have $ck=mn$, so maybe if I multiply this by $k$, I'm going to get somewhere. So $am=c$, let’s multiply by $k$, I get $amk=ck=mn$.
Now I have an $m$ on both sides, so either $m=0$ and in which case, $c=0$, and life is good. Or the alternative is that $ak=n$, which is the more interesting case.
So when $ak=n$, well what can I do? Well let me multiply both sides by $b$, so I get $abk=bn=c$, and that actually gives me my result.
Why do I know to multiply by $b$? Again because I'm trying to show $ab\mid c$, so if I multiply both sides by $b$, at least I get the $ab$ term and I get lucky and that the other side should equal $c$ because I need to reintroduce $c$ at some point and that's how I'm going to do that.
And hence $ab\mid c$.
So again, I think there's another way to do this question, but this is the way that I chose to do it. Again you could use GCDPF and if you want to you can, but the argument takes a little bit to write out and flush out so I'm not going to do it.
I'm going to use my head and try to be a little bit clever and try to avoid using GCDPF. Okay, but that's it. So here's a couple of examples of $\gcd$ problems and hopefully this gives you a little bit of a boost.