So to finish off…
so this is something that I like to do at this point.
Again, because I proved the Fundamental Theorem of Arithmetic last week,
up to this lemma. I now want to get
to this lemma as quickly as possible and I have done this.
Notice that this isn't cyclic in any way, shape, or form.
So, I mean, I could, you know,
I didn't use Euclid's Lemma anywhere else in the last couple of days before,
you know, going through the proof of the Fundamental -
or after going through the proof of the Fundamental Theorem of Arithmetic.
So there's no logical continuity errors, anything like that.
But I do like to use the Fundamental Theorem of Arithmetic to motivate this result
of Euclid's Lemma
because it is quite a…
it's surprisingly difficult to prove this, even though it looks very simple.
So what's Euclid's Lemma say again?
“If p is a prime number and p divides a b for integers a, b,
then p divides a, or p divides b.
Again, a good exercise: ask yourself, “What proof technique do I use here?”
I have an “or” in the conclusion.
A lot of the times it makes sense to use an argument by elimination.
So take one of these two things to be false,
so I'm just going to pick p divides a is false,
and I'm going to also assume the hypothesis,
so I'm going to suppose that p is prime, p divides a b,
and that p does not divide a, and I'm going to show that p divides b.
Again remember, why is this true? Well if p divides a, I'm done, right?
The conclusion’s true, the implication is therefore true.
I don't need to do anything. So I might as well start by assuming that p doesn't divide a.
So how do I link all this together? Why did I
need greatest common divisors to do this?
Okay so in some sense you never need something to do something else,
but it does help formulate the argument a lot nicer.
So since p doesn't divide a the gcd of p and a, that's equal to 1.
Well because it's equal to 1, well by Bézout’s Lemma,
again, I have a gcd condition, so I might as well use Bézout’s Lemma,
there exist integers x and y such that p x plus a y equals 1.
Now you look at this line, and maybe in a vacuum
you might wonder oh well why is this useful?
I mean, I don't really… I mean I want to show that p divides b and there's no b here.
So when you're doing something like this, I mean sometimes it might not be clear
why this is useful, right? I mean it doesn't look like I'm making any progress
towards getting p divides b,
but sometimes it helps to just write things down and play around with it.
In this case, it actually helps a lot because
now what we're going to do is multiply by b, we’re going to introduce b.
And so how do we do that? We're going to multiply everything by b, we get
p b x plus a b y is equal to p.
Now what do we have? Well p divides p, that's clear,
p divides a b, that was the hypothesis,
so thus by Divisibility of Integer Combinations,
we have that p divides p b x plus a b y,
and this value right here,
that's the same as this value right here. So that's equal to b, so hence p divides b,
And that's the end of the proof.
So this theorem is very easy to prove…well this lemma
is very easy to prove once you have the right tools.
Before having the right tools, this could be very tricky to prove.
I've actually tried it and not had much success.
You could probably do it if you're careful, but I haven't had success.
This being said, now we've reached the point where we're going to have a couple more theorems
that we've done through the week.
Again they're good practice, they just practice our tools, these theorems.
And again it's going get - there's a lot of names here, so don't
get overwhelmed, okay?
Just try to take it one at a time and
practice the mix, okay,
don't just practice one at a time. Practice one then practice another,
then go back to the first one, maybe go to another one, mix it up, okay?
Why do I say mix it up? Well because on an exam or on a test or in life,
things are going to be mixed up. It's not going to be hey just solve
this question using this technique. It's
going to take a little bit of thinking
to figure out which technique is good.
So first theorem that we have is GCD Of One, GCDOO.
“Let a and b be integers, then the greatest common divisor of a b is 1 if and only if
there exist integers x and y such that a x plus b y equals 1.”
This looks very similar to something that we did earlier.
That was one of the sample exercises.
But here's an “if and only if” statement so that extra “only if” part,
it's going to add us a little bit more work, but that's okay.
So to go in the implication direction: suppose that the gcd of a and b equals 1.
Again, we started with the gcd condition so we should probably use Bézout’s Lemma.
And it turns out that that's exactly going to work, right?
If we use Bézout’s Lemma, that's exactly the conclusion.
So that direction’s easy.
The other direction’s not too hard either though, right?
Suppose that there exist integers x and y such that a x plus b y equals 1.
So what can we do now? Now we want to conclude
something about the greatest common divisor,
so we should use the GCD Characterization Theorem,
and that's exactly what happens here.
So again, notice the difference here.
When we were proving the implication, we used Bézout’s Lemma
because the implication was in the - because the gcd was in the hypothesis,
and when we're proving the converse, we're using GCDCT
because now the greatest common divisor condition is in the conclusion.
So going through that thought, a x plus b y equals 1,
1 divides a, 1 divides B, 1 is equal to 1, 1 is greater than 0,
therefore by GCDCT. the gcd of a and b is 1.
And that's that. So it gives us a characterization of
when the gcd of a and b is 1.
Next one: Division By the GCD.
So let a and b be integers. If the gcd of a and b is equal to d
and d is not 0,
then the gcd of a over d comma b over d that's equal to 1.
Notice that we need the gcd…
that we need d to not be 0 because we want to divide by d,
so that's clearly an important condition here.
Now if we think about this, okay…
so what are we given? We're given a condition with the gcd, so
we're probably going to want to use Bézout’s Theorem,
and we need to conclude something about the gcd of something equaling 1,
so we're probably going to also want to use
the GCD Characterization Theorem, okay?
So...
So how do we go about this? So just try to do that exact thing, okay?
So now, again, maybe a good exercise,
pause the video and actually try to prove this. You should be able to prove this.
It actually is sort of a “follow your nose” kind of proof,
given that huge hint, okay?
So take a minute and try it.
Hopefully you've come back now.
Alright let's check out the proof.
Suppose that the gcd of a and b is equal to d which is not 0,
then by Bézout’s Lemma, there exist integers x and y such that
a x plus b y equals d.
So there's our use of Bézout’s Lemma.
Dividing by the non-zero d gives us that
a over d times x, plus b over d times y, is equal to 1.
Well now that we have this condition, this looks a lot like the last thing we just proved,
so now we can use that. By the GCD Of One condition, we know that
the gcd of a over d and b over d is equal to 1.
So you don't need to reprove things that we've proven, that's the emphasis off here.
But again remember so I did say, “Well we should use GCDCT.”
Okay, I didn't use GCDCT, well that's because
GCD Of One uses GCDCT, okay?
So there are lots of ways to prove this.
But again if you forget this theorem, it's fine to reprove it, that's perfectly fine.
If you wanted to use GCDCT it will work,
but you can make your life easier by also using GCD Of One.
I've made my life harder. Sometimes I like to do that.
Okay. One more,
Coprimeness and Divisibility. So,
if a, b, c are integers and c divides a b
and the gcd of a and c is 1,
then c divides b.
Again take a minute to try this out. This time I'm not going to give you hints, okay?
Pause the video, try this out.
It's a good exercise to do, it'll help you long-term.
So hopefully you've come back.
If you're stuck maybe as a hint:
notice that we have a gcd condition in the hypothesis,
so we should use…
what?
Alright let's check out the proof.
Okay,
so again assume the hypothesis, “Since the gcd of a and c is 1,
by Bézout’s Lemma, there exist integers x and y such that a x plus c y equals 1.”
It really is that sort of obvious.
If a gcd condition is in the hypothesis, then use Bézout’s Lemma.
Multiplying by b gives
a b x plus c b y is equal to b.
Since c divides a b and c divides c we can use…
oh wait what do we know?
Well what are we trying to show?
Oh, c divides a b and c divides c, then
I guess c must divide b, well that was easy.
What did I do? I actually reproved DIC here.
Oh well that's okay.
So since either c divides a b there exists an integer k such that a b is equal to c k.
Substituting gives c k x plus c b y is equal to b.
Thus c times k x plus b y equals b and so c divides b.
Again you can use DIC here or you can go directly by the definition.
I guess it's good to practice doing different things.
Remind ourselves what the definition of divisibility is etc.
But yeah DIC would just crush it from here.
C divides a b, c divides c so
therefore c divides a b x plus c b y which is b by DIC.