Hello everyone. In this video, we're going to continue our exam review.
So we have here question 4. If a, b, c are integers
with c dividing a b and the gcd of a and c is 1, then c divides b.
So with a question like this, since the gcd condition is
in the hypotheses, 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. So since the gcd of a and c is 1,
we may apply Bézout’s Lemma, or the Extended Euclidean Algorithm, to see that
there are integers x and y such that a x plus c y equals 1.
So let me maybe write it in. See that
there exist
integers x and y
such that…
let's fix that up.
So a x plus c y equals 1, okay?
Now I want to show that c divides b, and I know that c divides a b,
so I got to get a b to appear in here.
So in order to do that, I'm going to multiply everything by b.
So multiply through by b gives a b x plus c b y equals b.
So now c divides a b, and c divides
c, so it divides c b y,
and so by Divisibility of Integer Combinations, well
c divides this, c divides this therefore c divides b.
And that completes the proof.
So that's good, that was not too, too bad.
For part 2, prove for integers a, b, c
such that the gcd of a and b is 1, if
a divides c and b divides c, then a b divides c.
So the way - 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 divides c and b divides c, and
a and b don't share any prime factors, then the product should 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 the gcd of a and b is 1, so I'm going to
throw it into the EEA, or Bézout’s Lemma whatever you want to call it.
So a x plus b y
equals 1.
So I guess I skipped a step, so that's sort of my starting point is taking this. Now
once I have that a x plus b y equals 1, I’m in sort of a pickle, right, I don't really know what to do.
So maybe I should read my first sentence which I wrote
by definition there exist integers m and n such that
a m equals c and b n equals c.
So I'm going to unwind the definition of divisibility,
and try to use that with the combination of a x plus b y equals 1.
So the combination of those two facts should get me somewhere.
Now I want a m and b n to appear, so I should probably multiply everything by m n, okay?
So I'm going to do that, and 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 when a m is c, I’m going to substitute that in, and
b n is c, so I'm going to substitute that in.
So I know c divides this and c divides the second term, so c should divide m n.
So again by definition, there exists a k such that
c k is equal to m n.
So maybe I should write down for some integer k.
So let's do that. Okay.
Now what do we know? Okay, so c k equals m n, okay? So
where do I go? Let's go back to a m equals c.
Now I know that I have c k is equal to m n,
so maybe if I multiply this by k, I'm going to get somewhere.
So a m equals c, let’s multiply by k,
I get a m k, which is c k, which is m n.
Now I have an m on both sides,
so either m is 0 and in which case…
if m is 0, then c is 0, and life is good.
So maybe I should mention that.
So in the case where a m k is equal to m n, well either m is 0,
and if m is 0 then a times m is c, so c is 0,
and the claim is true because every number divides 0, that's okay,
right, 0 times any number is equal to 0, so any number divides 0.
Or the alternative is that a k is equal to n, which is the more interesting case.
So when a k equals n, well what can I do?
Well let me multiply both sides by b, so I get a b k is equal to b n,
and lo and behold, b n is actually equal to c,
and that actually gives me my result. Why do I know to multiply by b?
Again because I'm trying to show a b divides c,
so if I multiply both sides by b, at least I get the a b term
and I get lucky in 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 a b divides 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 be a little bit…
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.